프로그래머스 Lv.4) 지형 이동

지형이동

프로그래머스

풀이

언젠가 풀었던 문제인 것 같기도 하고.. 아닌 것 같기도 하다. 아무튼 처음에 생각한 것은 for문을 돌면서 dp로 최소 값을 누적해가는? 로직으로 풀었는데 많이 틀린 것을 보고 이 로직은 풀 수 없다고 판단했다. MST에 약하다고 생각해서 최대한 기피하려고 했지만, 검색이나 다시 생각해봐도 MST를 통해 풀어야겠다는 생각이 들었다.

 

1. 사다리 없이 이동할 수 있는 섹터를 Grouping 해준다.

2. 각 구역에서 다른 구역으로 이동하는 경우에 두 그룹의 넘버와 사다리의 비용을 우선순위 큐에 저장한다.

3. poll 하면서 두 구역을 union한다.

 

추가로 만든 클래스는 입맛대로 우선순위 큐에 넣기 위한 Node 클래스와 포지션을 쉽게 저장하기 위한 Pos 클래스이다.

이외의 메소드들은 out of idx 방지나 문제의 조건에 따라 height 이하인지 아닌지 구분하는 것과 위의 1,2,3번에서 필요한 메소드이다.

 

코드

import java.util.*;

public class MovingLand_62050 {
    static int[] dx = {0,1,0,-1};   // x축 이동    0 : 북, 1 : 동, 2 : 남, 3 : 서
    static int[] dy = {1,0,-1,0};   // y축 이동
    static int[] parents;
    static int[][] visit;
    static PriorityQueue<Node> ladderQueue;

    private static int solution(int[][] land, int height) {
        initVisit(land.length);
        int group =1;

        //grouping
        for(int y=0; y<land.length; y++) {
            for(int x=0; x<land.length; x++) {
                if(visit[y][x] ==0) {   //구역이 없는 경우
                    grouping(new Pos(x,y),land,height,group++);
                }
            }
        }

        //initialize parents
        inItParents(group);

        //initialize ladder PQ
        ladderQueue = new PriorityQueue<>();

        //save the ladder pq
        for(int y=0; y<land.length; y++) {
            for(int x=0; x<land.length; x++) {
                findOtherGroup(x,y,land);
            }
        }

        return getMinLadder(group-2);   // n-1개 연결하면 됨
    }

    private static int getMinLadder(int total) {
        int result =0;
        // find min ladder cost
        while(total >0) {
            Node node = ladderQueue.poll();
            if(find(node.group1) != find(node.group2)) {
                union(node.group1, node.group2);
                result += node.diff;
                total--;
            }
        }
        return result;
    }

    private static void findOtherGroup(int originX, int originY, int[][] land) {
        for(int i=0; i<4; i++) {
            int x = originX + dx[i];
            int y = originY + dy[i];
            if(isInArea(x,y,land.length)) { // out of idx 방지
                if(visit[originY][originX] != visit[y][x]) { // 다른 그룹이면
                    ladderQueue.offer(new Node(visit[originY][originX], visit[y][x], Math.abs(land[y][x] - land[originY][originX])));
                }
            }
        }
    }

    private static void grouping(Pos pos, int[][] land, int height, int group) {
        Queue<Pos> queue = new LinkedList<>();
        queue.offer(pos);
        visit[pos.y][pos.x] = group;
        while(!queue.isEmpty()) {
            Pos tmp = queue.poll();
            for(int i=0; i<4; i++) {
                int x = tmp.x+dx[i];
                int y = tmp.y+dy[i];
                if(isInArea(x,y, land.length)) {
                    if(visit[y][x] ==0 && canMove(land[tmp.y][tmp.x], land[y][x], height)) {
                        queue.offer(new Pos(x,y));
                        visit[y][x] = group;
                    }
                }
            }
        }
    }

    private static boolean canMove(int num1, int num2, int height) {    // move without ladder
        return Math.abs(num1-num2) <= height ? true : false;
    }

    private static boolean isInArea(int x, int y, int n) {
        return x>=0 && x<n && y>=0 && y<n ? true : false;
    }

    private static void initVisit(int n) {
        visit = new int[n][n];
    }

    private static void inItParents(int n) {
        parents = new int[n];
        for(int i=1; i<n; i++) {
            parents[i] = i;
        }
    }

    private static void union(int val1, int val2) {
        val1 = find(val1);
        val2 = find(val2);
        if(val1 < val2) {
            parents[val2] = val1;
        } else {
            parents[val1] = val2;
        }
    }

    private static int find(int value) {
        if(value == parents[value]) {
            return value;
        }
        return parents[value] = find(parents[value]);
    }

    public static void main(String[] args) {
//        int[][] land = {{1, 4, 8, 10}, {5, 5, 5, 5}, {10, 10, 10, 10}, {10, 10, 10, 20}};
//        int height = 3;
        int[][] land = {{10, 11, 10, 11}, {2, 21, 20, 10}, {1, 20, 21, 11}, {2, 1, 2, 1}};
        int height = 1;
        System.out.println(solution(land,height));
    }
}

class Pos {
    int x;
    int y;

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

class Node implements Comparable<Node>{
    int group1;
    int group2;
    int diff;

    public Node(int group1, int group2, int diff) {
        this.group1 = group1;
        this.group2 = group2;
        this.diff = diff;
    }

    @Override
    public int compareTo(Node o) {
        if(this.diff > o.diff) {
            return 1;
        } else if (this.diff == o.diff) {
            return this.group1 > o.group1 ? 1 : -1;
        } else {
            return -1;
        }
    }
}