[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;
    }
}