문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/62050?language=java
문제 설명
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 이하인 자연수입니다.
입출력 예 (각각 land, height , result )
[[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
문제 풀이
처음에는 이걸 DFS로 쭉 갈 수 있는 지 없는 지 체크하면서 방문하면 되겠다라고 생각했다가 그렇게 해서는 최소비용을 알아낼 수 없을 것 같아 prim을 이용하는 것이 좋겠다는 생각이 들었다.
그래서 먼저 0,0 부터 시작해서 3,3까지의 각각의 칸을 노드로 생각하고 상, 하, 좌, 우 연결을 해주었다.
나는 이것을 0,0 = 0번째 노드 , 0,1 = 1번째 노드 ... 3,3은 15번째 노드로 변환하고 이들을 prim 알고리즘(최소 신장 트리) 를 통해 최소 비용으로 모두 연결 시키면 되겠다! 라는 결론을 내리게 되었고 코드를 구현하니 다행히도 정답을 맞출 수 있었다!
즉 정리하자면
-
Prim 알고리즘을 적용하기 위해 각 노드들을 연결해준다.
-
연결 시 가중치는 각 칸 사이의 높이 차이인데 height 이하면 0으로 해주었다.
-
그 다음은 Prim 알고리즘을 적용해 최소 비용을 찾으면 된다.
import java.util.*;
public class exam02_1 {
final static int[][] dirs = {{1,0},{0,1},{-1,0},{0,-1}};
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;
System.out.println(solution(land,height));
land = new int[][]{{10, 11, 10, 11}, {2, 21, 20, 10}, {1, 20, 21, 11}, {2, 1, 2, 1}};
height = 3;
System.out.println(solution(land,height));
}
static class Node{
int to;
int weight;
public Node(int to, int weight) {
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return "Node{" +
"to=" + to +
", weight=" + weight +
'}';
}
}
static List<List<Node>> graph;
public static int solution(int[][] land, int height) {
graph = new ArrayList<>();
int v = land.length * land[0].length;
System.out.println("v = " + v);
for (int i = 0; i < v; i++) {
graph.add(new ArrayList<>());
}
link(land, height); //prim 알고리즘을 적용하기 위해 각 노드들을 연결
System.out.println(graph);
return prim(v, 0);
}
private static int prim(int v, int start) {
PriorityQueue<Node> pq = new PriorityQueue<>((x,y) -> x.weight - y.weight);
boolean[] visited = new boolean[v];
int weightSum = 0;
pq.add(new Node(start, 0));
while (!pq.isEmpty()){
Node cur = pq.poll();
if(visited[cur.to]){
continue;
}
visited[cur.to] = true;
weightSum += cur.weight;
System.out.println("weightSum = " + weightSum);
for(Node adj : graph.get(cur.to)){
if(!visited[adj.to]){
pq.add(adj);
}
}
}
return weightSum;
}
private static void link(int[][] land, int height) {
for (int i = 0; i < land.length; i++) {
for (int j = 0; j < land.length; j++) {
for(int[] dir : dirs) {
int nX = i + dir[0];
int nY = j + dir[1];
if (nX < 0 || nY < 0 || nX >= land.length || nY >= land[0].length) {
continue;
}
int idx = i * (land.length-1) + j;
if(i!=0){
idx+= i;
}
int nIdx = nX * (land.length-1) + nY;
if(nX!=0){
nIdx+= nX;
}
int weight = 0;
if(Math.abs(land[i][j] - land[nX][nY]) > height){
weight = Math.abs(land[i][j] - land[nX][nY]);
}
graph.get(idx).add(new Node(nIdx, weight));
graph.get(nIdx).add(new Node(idx, weight));
}
}
}
}}
