[프로그래머스] 62050 지형 이동 - JAVA
문제
https://school.programmers.co.kr/learn/courses/30/lessons/62050
문제 분석
조건
`N x N` 크기의 땅의 각 칸에는 높이 정보가 있다. 상하좌우로 인접한 칸으로 이동할 때, 두 칸의 높이 차이가 `height` 이하라면 비용이 들지 않는다. 하지만 높이 차이가 `height`를 초과하면, 그 차이만큼의 비용을 내고 사다리를 놓아야만 이동할 수 있다.
이때, 모든 땅을 서로 오고 갈 수 있도록 연결하는 데 필요한 사다리 비용의 최솟값총합을 구하는 문제
풀이방법
그래프의 모든 정점을 최소 비용으로 연결하는 최소 신장 트리(MST)를 이용해 문제를 해결하였다.
`Ladder` 클래스: 다음으로 이동할 칸의 정보(`pos`)와 그곳으로 가는 데 필요한 비용(`cost`)을 함께 저장하는 클래스를 정의했다.
예제 1번을 통해 MST 알고리즘으로 문제를 풀이하면,
사다리가 없이 이동 가능한 거리는 3인 예제 1번의 초기상태는 위와 같다. 제일 먼저 `0, 0`좌표와 함께 `cost`가 0으로 큐에 들어가며 탐색이 시작된다.
큐에서 나온 `0, 0`은 방문처리가 되며, 상하좌우를 탐색하며 방문하지 않은 점을 우선순위큐에 넣게 된다. 우선순위 큐는 `cost`가 적은 순으로 정렬이 된다. 아래쪽으로 `1, 0` 좌표로는 높이 차이가 4가 발생하기 때문에 사다리 비용 4가 발생하지만, 오른쪽 좌표인 `0, 1`은 사다리 없이 이동 가능한 거리인 3의 높이 차이이므로 사다리 비용이 0이 된다.
큐에서 나온 `0, 1`은 이전에 방문하지 않았으므로 방문처리가 되며, 상하좌우에서 방문기록이 없는 두 좌표를 큐에 넣게 된다.
`1, 1`에서 다시 상하좌우를 탐색하면 위처럼 큐에 추가가 된다. `1, 0`은 이미 큐에 들어있는 좌표지만 해당 좌표로 가기 위한 cost가 다르고 방문하지 않았기 때문에 큐에 들어갈 수 있다.
그 후 탐색을 진행하다 보면 큐에서 이전에 넣었던 `[4, (1, 0)]`이 나오게 되지만, 이미 `1, 0`은 방문처리가 된 이후므로 탐색을 진행하지 않고 넘어간다. 그 후 `[5, (2, 1)]`이 큐에서 나왔을 때, 방문했던 지점이 아니므로 방문처리를 하며, cost가 정답에 더해지게 된다.
이를 큐가 비게 될때까지 진행하게 되면 정답이 된다. 필자는 이때 초기 땅의 수를 모두 구한 뒤, 방문처리를 할 때마다 남은 땅의 수를 감소시켰고 0이 되면 바로 종료하도록 구현하였다.
코드
import java.util.*;
class Ladder implements Comparable<Ladder> {
int cost;
int[] pos;
public Ladder(int cost, int[] pos) {
this.cost = cost;
this.pos = pos;
}
@Override
public int compareTo(Ladder o) {
return this.cost - o.cost;
}
}
class Solution {
static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int solution(int[][] land, int height) {
int answer = 0;
boolean[][] visited = new boolean[land.length][land.length];
int remainCount = land.length * land.length; // 방문하지 않은 좌표의 수
PriorityQueue<Ladder> queue = new PriorityQueue<>();
queue.add(new Ladder(0, new int[]{0, 0}));
while (!queue.isEmpty()) {
Ladder now = queue.poll();
if (visited[now.pos[0]][now.pos[1]]) { // 방문 한 지점이면 넘어감
continue;
}
visited[now.pos[0]][now.pos[1]] = true;
remainCount--;
answer += now.cost; // 사다리 가치 더함.(사다리 필요 없으면 0)
if (remainCount == 0) {
break;
}
for (int[] dir : dirs) {
int r = now.pos[0] + dir[0];
int c = now.pos[1] + dir[1];
if (isInvalid(r, c, land.length) || visited[r][c]) {
continue;
}
int diff = Math.abs(land[now.pos[0]][now.pos[1]] - land[r][c]);
if (diff <= height) { // 사다리 길이보다 짧으면 사다리 비용 0
queue.add(new Ladder(0, new int[]{r, c}));
} else {
queue.add(new Ladder(diff, new int[]{r, c}));
}
}
}
return answer;
}
private boolean isInvalid(int r, int c, int length) {
return r < 0 || c < 0 || r >= length || c >= length;
}
}허거덩
정답을 맞추고 나면 효율적으로 잘 짠 코드인지, 낭비되는 부분은 없는 편인지 제미나이나 GPT에게 코드 피드백을 요청하는 편이다.
문제를 보고 종이에 이런 식으로..? 오호.. 그저 그런 BFS구만 쉽구만 이게 레벨 4? 하며 후다닥 풀고 피드백을 요청했는데,
예..? MST... 어라? 생각해보니 정말 최소 신장 트리 문제였고...ㅋ 최소 신장트리 문제를 BFS 탐색용 Queue 1개와 사다리 관리용 Queue 1개로 총 2개의 Queue로 문제를 풀고 있었다.
답도 맞았고 따지고 보면 제미나이 말처럼 MST 알고리즘을 구현하긴 했지만 더 좋은 코드가 있다는 것을 알아버렸고... 다시 풀 수밖에... 사실 그냥 큐 합치는 거지만... 그래도 합치니까 코드 반토막..ㅋ 으이그 다 까먹을 거 왜 공부하냐