[ 프로그래머스 ] Level4 - 지형 이동 (Java : Prim 알고리즘 )

그래프 탐색 아는 알고리즘이라고 사실 크루스칼이랑 프림이 있지만, 나는 프림이 편해서 항상 프림만 쓴다...

사실 프림 알고리즘에 대해서 학습한지도 얼마 되지 않았지만 한번 외워서 코딩하니까 되더라..!

[ Summer/Winter Coding(2019) ] 지형이동 - Level 4.

 

문제 설명

N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.

이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.

각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.

제한사항

• land는 N x N크기인 2차원 배열입니다.
• land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
• land의 원소는 각 격자 칸의 높이를 나타냅니다.
• 격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
• height는 1 이상 10,000 이하인 자연수입니다.

---

입출력 예

landheightresult

[[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]]	3	15
[[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]]	1	18

입출력 예 설명

입출력 예 #1

각 칸의 높이는 다음과 같으며, 높이차가 3 이하인 경우 사다리 없이 이동이 가능합니다.

위 그림에서 사다리를 이용하지 않고 이동 가능한 범위는 같은 색으로 칠해져 있습니다. 예를 들어 (1행 2열) 높이 4인 칸에서 (1행 3열) 높이 8인 칸으로 직접 이동할 수는 없지만, 높이가 5인 칸을 이용하면 사다리를 사용하지 않고 이동할 수 있습니다.

따라서 다음과 같이 사다리 두 개만 설치하면 모든 칸을 방문할 수 있고 최소 비용은 15가 됩니다.

• 높이 5인 칸 → 높이 10인 칸 : 비용 5
• 높이 10인 칸 → 높이 20인 칸 : 비용 10

입출력 예 #2

각 칸의 높이는 다음과 같으며, 높이차가 1 이하인 경우 사다리 없이 이동이 가능합니다.

위 그림과 같이 (2행 1열) → (1행 1열), (1행 2열) → (2행 2열) 두 곳에 사다리를 설치하면 설치비용이 18로 최소가 됩니다.

 

문제 설명은 위와 같다. 문제를 읽어보면 모든 곳을 방문하는 그래프를 구하는 "최소비용트리(MST)"를 구하는 문제라는 것을 알 수 있다.  간선이 많을 경우 크루스칼, 간선이 적을 경우 프림을 쓰라고 하지만...

난 항상 프림만 쓴다.. 크루스칼 코딩 못하겠다...

순환 그래프 탐색으로 적용되어 최소값을 찾는 알고리즘이다.

처음에는 이해하기 어려웠지만 한번 이해하니 쏙쏙 들어온다... Queue값에 방문한 노드들을 넣어둔다. 그리고 방문한 노드들 중에서 가장 비용으로 방문할 수 있는 곳을 Queue에 다시 넣어두는 방식이다. 

사용한 코드를 먼저 첨부하고 설명을 하겠다. 

import java.util.*;
class Solution {
        public int solution(int[][] land, int height) {
            int answer = 0;
            int N = land.length;
            boolean [][]visitied = new boolean[N][N];
            visitied[0][0] = true;
            Queue<int[]> q= new LinkedList<int[]>();
            q.add(new int[] {0,0});
            Queue<int[]> dq = new LinkedList<int[]>();
            PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0]-o2[0];
                }
            });
            while(!q.isEmpty() && dq.size()<=N*N) {
                int size =q.size();
                while(!q.isEmpty()) {
                    int []t = q.poll();
                    int r = t[0], c = t[1];
                    if(r>0 && !visitied[r-1][c]) {
                        int cost = Math.abs(land[r][c]-land[r-1][c])>height? Math.abs(land[r][c]-land[r-1][c]):0;
                        if(cost==0) {
                            q.add(new int[] {r-1,c});
                            visitied[r-1][c]=true;
                        }else pq.add(new int[] {cost,r-1,c});
                    }
                    if(c>0 && !visitied[r][c-1]) {
                        int cost = Math.abs(land[r][c]-land[r][c-1])>height? Math.abs(land[r][c]-land[r][c-1]):0;
                        if(cost==0) {
                            q.add(new int[] {r,c-1});
                            visitied[r][c-1]=true;
                        }else pq.add(new int[] {cost,r,c-1});
                    }
                    if(r<N-1 && !visitied[r+1][c]) {
                        int cost = Math.abs(land[r][c]-land[r+1][c])>height? Math.abs(land[r][c]-land[r+1][c]):0;
                        if(cost==0) {
                            q.add(new int[] {r+1,c});
                            visitied[r+1][c]=true;
                        }else pq.add(new int[] {cost,r+1,c});
                    }
                    if(c<N-1 && !visitied[r][c+1]) {
                        int cost = Math.abs(land[r][c]-land[r][c+1])>height? Math.abs(land[r][c]-land[r][c+1]):0;
                        if(cost==0) {
                            q.add(new int[] {r,c+1});
                            visitied[r][c+1]=true;
                        }else pq.add(new int[] {cost,r,c+1});
                    }
                    dq.add(t);
                }
                while(!pq.isEmpty()) {
                    int t[] = pq.poll();
                    if(visitied[t[1]][t[2]])continue;
                    answer+=t[0];
                    q.add(new int[] {t[1],t[2]});
                    visitied[t[1]][t[2]]=true;
                    break;
                }
            }
            return answer;
        }
}

 

여기에서 visitied를 통해 방문했던 노드인지 아닌지를 확인하도록 한다. dq라는 값에 방문+주변탐색까지 한 노드들을 넣어놓아서, dq.contains()를 이용해도 되지만, visitied[][]를 이용해서 확인하였다. 

그래프의 노드들을 넣어둘 리스트는 총 세개가 필요한데, 처음 Queue<> q는 아직 최소비용 연결점 탐색을 하지 않은 노드를 넣어놓는 배열으로, while문을 돌때 사용한다. q는 특히 cost가 0인 경우가 있는 이러한 문제에서 유용하게 사용되었다. cost가 0이라면 그래프에 바로 추가한 다음 최소비용 간선 탐색이 가능하기 때문이다.

그리고 이렇게  q를 순회하면서 탐색되어서, cost가 height보다 큰 값들은 PriorityQueue<> pq에 저장된다. 사다리가 놓아질 수 있는 위치들을 확인하면서 돌게 된다.  

while(!q.isEmpty()){} 구문이 끝났다는 것은 cost가 0인 값들을 모두 돌았으니, 사다리를 놓아야하는 것을 의미한다.

PriorityQueue<>pq에서 가장 비용이 작은 순으로 정렬이 되니, 방문을 안한 노드를 연결하는 점중 가장 먼저 poll()되는 값을 사다리로 연결시키면 최소 비용으로 노드가 연결되게 된다. 이 경우 이전에 q-> dq의 과정에서 방문이 되었지만 사다리로 연결될 수 있는 경우가 포함되어 있기 때문에 if(visitied[t[1]][t[2]])를 통해서 검사를 해 준 이후 값을 넣어야 한다. 사다리를 최소 비용으로 하기 위해 하나만 노드에 넣고, 그 이후로 다시 while문을 돌면서 모든 노드가 방문처리되게 한다. 

이러한 방법을 사용하면 모든 노드들을 방문한 최소비용트리가 완성된다. 

시간과 결과는 아래 그림으로 첨부한다.