지형 이동

[geonnho0]

문제 링크

[geonnho0]

기존 아이디어 - 시간 초과 발생

처음 생각한 방법은 (0, 0)에서 bfs를 통해 인접 칸들을 방문하고, 방문한 모든 칸에 대해서 최소 높이 차를 가지는 방문하지 않은 칸을 찾아요. 해당 방문하지 않은 칸에 도달하기 위해 사다리를 설치한 뒤, 해당 칸부터 bfs를 탐색해요.

위 과정을 반복하면서, 사다리를 놓을 만한 곳을 찾지 못한다면, 모든 칸들을 방문한 것으로 볼 수 있고, 사다리를 놓을 때마다 높이 차를 정답에 더해주면 돼요.

개선 아이디어 - 우선순위 큐 사용

시간 초과가 발생하기 때문에, 사다리를 놓을 만한 곳을 매번 찾으려면 O(N^2)의 시간 복잡도가 발생해요. 사다리를 찾는 함수는 최악의 경우 N번 발생할 수 있기 때문에 시간 소모가 커지게 돼요.

따라서, (0,0)에서 bfs를 통해 방문할 수 있는 인접 칸들을 방문하면서, 인접 칸에서 아직 방문하지 않은 칸에 사다리를 놓는다고 가정하고, 해당 사다리 정보를 우선순위 큐에 저장해요.

1. 우선순위 큐에는 (방문하지 않은 칸의 좌표, 높이 차)를 저장하고, 높이 차를 오름차순으로 정렬해요.
2. 매번 bfs를 할 때, 시작 노드로 우선순위 큐에서 좌표를 가져와요.
3. 우선순위 큐에서 가져온 좌표는 이전 bfs 과정에서 방문되었을 수도 있기 때문에, 방문하지 않을 경우에만 bfs를 진행하고, 방문했을 경우 다시 우선순위 큐에서 다음 좌표를 가져와요.

코드

class Solution {
    int[][] land;
    boolean[][] visited;
    int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    int height, N, answer;
    PriorityQueue<int[]> pqueue = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);

    public int solution(int[][] land, int height) {
        init(land, height);
        pqueue.offer(new int[]{0, 0, 0});
        while (!pqueue.isEmpty()) {
            int[] next = pqueue.poll();
            if (visited[next[0]][next[1]])
                continue;
            answer += next[2];
            bfs(next);
        }
        return answer;
    }

    void init(int[][] land, int height) {
        N = land.length;
        this.land = land;
        visited = new boolean[N][N];
        this.height = height;
        answer = 0;
    }

    void bfs(int[] start) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = curr[0] + dx[i], nextY = curr[1] + dy[i];
                if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N)
                    continue;
                if (visited[nextX][nextY])
                    continue;
                int sub = Math.abs(land[nextX][nextY] - land[curr[0]][curr[1]]);
                if (sub > height) {
                    pqueue.offer(new int[]{nextX, nextY, sub});
                    continue;
                }
                visited[nextX][nextY] = true;
                queue.offer(new int[]{nextX, nextY});
            }
        }
    }
}