[Programmers] μ§€ν˜• 이동

[Programmers] μ§€ν˜• 이동 JAVA

문제 : μ§€ν˜• 이동

문제 μ„€λͺ…

N * N 크기의 μ§€ν˜•μ΄ 있고 μ§€ν˜•λ§ˆλ‹€ 각각의 높이가 μžˆμŠ΅λ‹ˆλ‹€.
μ§€ν˜•μ˜ 높이차가 정해진 κ°’ μ΄ν•˜μ΄λ©΄ 자유둭게 이동할 수 μžˆμ§€λ§Œ, 정해진 κ°’ 보닀 차이가 λ†’μœΌλ©΄ 사닀리λ₯Ό μ„€μΉ˜ν•΄μ•Ό 이동할 수 μžˆμŠ΅λ‹ˆλ‹€.
μ΄λ•Œ μ‚¬λ‹€λ¦¬μ˜ λ†’μ΄λŠ” μΈμ ‘ν•œ μ§€ν˜•μ˜ 높이 차이고, μ‚¬λ‹€λ¦¬μ˜ μˆ˜λŠ” μ œν•œμ΄ μ—†μ§€λ§Œ μ‚¬λ‹€λ¦¬λ“€μ˜ 높이합이 μ΅œμ†Œν•œμ΄ λ˜λ„λ‘ μ„€μΉ˜ν•˜μ—¬ λͺ¨λ“  μ§€ν˜•λΌλ¦¬ μ—°κ²°λ˜κ²Œ ν•΄μ•Ό ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€.


Solution

bfs, 크루슀칼 μ•Œκ³ λ¦¬μ¦˜

μš°μ„  bfs둜 μ„œλ‘œ 사닀리 없이 이동할 수 μžˆλŠ” μ§€ν˜•λ“€μ„ ꡬ별해 μ£Όκ³  각각 번호(사닀리 없이 이동할 수 μžˆλŠ” 지역별 번호)λ₯Ό ν• λ‹Ήν•΄ μ€λ‹ˆλ‹€.
μ΄λ•Œ μΈμ ‘ν•œ μ§€ν˜•μ˜ 높이차가 주어진 κ°’ 보닀 μ»€μ„œ 이동을 λͺ»ν•˜λŠ” μ§€ν˜•μ—μ„œλŠ” 크루슀칼 μ•Œκ³ λ¦¬μ¦˜μ„ μˆ˜ν–‰ν•˜κΈ° μœ„ν•œ μ½”λ“œλ₯Ό μž‘μ„±ν•΄ μ£Όμ–΄μ•Ό ν•©λ‹ˆλ‹€.
λ§Œμ•½ 높이차가 크게 차이 λ‚˜λŠ” μ§€ν˜•μ΄ λ°©λ¬Έν•œ 적 μ—†λŠ”(지역별 λ²ˆν˜Έκ°€ μ—†λŠ” κ³³)이라면 λ¬΄μ‹œν•˜κ³  continue ν•΄μ€λ‹ˆλ‹€. 높이차가 크게 λ‚˜λŠ” μ§€ν˜•μ΄ 지역별 λ²ˆν˜Έκ°€ ν• λ‹ΉλΌμžˆλŠ” μ§€ν˜•μ΄λΌλ©΄ ν˜„μž¬ μ§€ν˜•μ˜ 지역 번호, 사닀리가 μžˆμ–΄μ•Ό 갈 수 μžˆλŠ” μ§€ν˜•μ˜ 지역 번호, 높이차 μ„Έ 가지 값을 높이차λ₯Ό κΈ°μ€€μœΌλ‘œ μš°μ„ μˆœμœ„ 큐에 λ‹΄μ•„μ£Όμ—ˆμŠ΅λ‹ˆλ‹€.
λͺ¨λ“  μ§€ν˜•μ„ μˆœνšŒν•˜λ©΄μ„œ 사닀리가 ν•„μš”ν•œ 곳을 μš°μ„ μˆœμœ„ 큐에 λͺ¨λ‘ 담아쀬닀면, 높이차가 κ°€μž₯ 적은 지역을 ν•©μ³μ£Όλ©΄μ„œ μœ λ‹ˆμ˜¨ νŒŒμΈλ“œλ₯Ό μ΄μš©ν•΄ 크루슀칼 μ•Œκ³ λ¦¬μ¦˜μ„ μ‹€ν–‰ν•©λ‹ˆλ‹€.
μ΄λ ‡κ²Œ 이어진 μ΅œμ†Œ μ‹ μž₯ 트리λ₯Ό λ§Œλ“€λ©΄μ„œ μ‚¬μš©ν•œ μ‚¬λ‹€λ¦¬μ˜ 총합을 return ν•΄μ€λ‹ˆλ‹€.


Description

  • μš°μ„ μˆœμœ„ 큐에 λ‹΄μ•„μ•Ό ν•˜λŠ” ν˜„μž¬ μ§€ν˜•μ˜ 지역 번호, 사닀리가 μžˆμ–΄μ•Ό 갈 수 μžˆλŠ” μ§€ν˜•μ˜ 지역 번호, 높이 μ°¨λ₯Ό GuardλΌλŠ” 클래슀둜 λ‹΄μ•˜μŠ΅λ‹ˆλ‹€.
  • vis[][] 배열에 사닀리 없이 이동할 수 μžˆλŠ” 지역별 번호λ₯Ό 1μ”© μ¦κ°€μ‹œν‚€λ©΄μ„œ λ‹΄μ•˜μŠ΅λ‹ˆλ‹€.

μ†ŒμŠ€μ½”λ“œ

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
class Guard implements Comparable<Guard>{
    private int st;
    private int ed;
    private int value;

    public int getValue() {
        return value;
    }

    public int getEd() {
        return ed;
    }

    public int getSt() {
        return st;
    }

    public Guard(int st, int ed, int value){
        this.st = st;
        this.ed = ed;
        this.value = value;
    }

    @Override
    public int compareTo(Guard o) {
        return Integer.compare(this.value, o.value);
    }
}
class Node{
    private int x;
    private int y;

    public int getY() {
        return y;
    }

    public int getX() {
        return x;
    }

    public Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}

class Solution {
    public static int[] parent;
    public static int find(int idx){
        if(idx==parent[idx]) return idx;
        else return parent[idx] = find(parent[idx]);
    }
    public static void merge(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        if(a>b) parent[a] = b;
        else parent[b] = a;
    }
    public static PriorityQueue<Guard> pq = new PriorityQueue<>();
    public static int[][] vis;
    public static int[][] map;
    public static int n;
    public static int len;
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {1, -1, 0, 0};
    public static int cnt;

    public void bfs(int nowX, int nowY){
        vis[nowX][nowY] = cnt;
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(nowX,nowY));
        while(!q.isEmpty()){
            Node node = q.poll();
            int x = node.getX();
            int y = node.getY();
            for(int i=0; i<4; i++){
                int nx = x+dx[i];
                int ny = y +dy[i];
                if(nx<0||ny<0||nx>=n||ny>=n) continue;
                if(Math.abs(map[x][y]-map[nx][ny])> len) {
                    if(vis[nx][ny] != 0){
                        pq.offer(new Guard(vis[x][y],vis[nx][ny],Math.abs(map[x][y]-map[nx][ny])));
                    }
                    continue;
                }
                if(vis[nx][ny]!=0) continue;
                else{
                    vis[nx][ny] = cnt;
                    q.offer(new Node(nx,ny));
                }
            }
        }
    }


    public int solution(int[][] land, int height) {
        n = land.length;
        map = new int[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                map[i][j] = land[i][j];
            }
        }
        len = height;
        vis = new int[n][n];
        for(int i =0; i<n; i++){
            for(int j=0; j<n; j++){
                if(vis[i][j]==0){
                    cnt++;
                    bfs(i,j);
                }
            }
        }
        parent = new int[cnt+1];
        int res = 0;
        for(int i=0; i<=cnt; i++) parent[i] = i;
        while (!pq.isEmpty()){
            Guard guard = pq.poll();
            int st = guard.getSt();
            int ed =guard.getEd();
            int value =guard.getValue();

            if(find(st)==find(ed)) continue;
            else if(st==0||ed==0) continue;
            else {
                merge(st,ed);
                res += value;
            }
        }
        return res;
    }
}