p.g. 490의 '풀이 1 다익스트라 알고리즘 구현'

[hoogom88]

제가 가지고 있는 전자책은 2023년 10월 20일 버전 1.0 입니다.

p.g. 490의 '풀이 1 다익스트라 알고리즘 구현'의 풀이에 질문이 있어 문의 드립니다.

본 풀이는 격자 모양을 사방이 거리 1인 노드로 연결된 그래프로 두고, 다익스트라 알고리즘으로 해결하고 있습니다.
하지만 이는 적절하지 않은 풀이입니다.

각 노드 사이의 거리가 1이기 때문에, 다익스트라 알고리즘으로 풀었을 때의 아무런 이점이 없습니다.
동작 방식이 아래의 BFS코드와 완전히 동일하며, 유일한 차이는 우선순위큐의 유무이지만 우선순위큐를 사용하는 것이 아래의 이유로 손해입니다.

• 특정 노드와 연결된 모든 모든 노드와의 거리가 동일하기 때문에 탐색의 우선순위가 없습니다.
• 우선순위 큐를 사용하면 다음 탐색 후보 노드 삽입과 탐색 노드 추출에서 O(log n)으로 오히려 손해를 보게됩니다.
  (BFS 풀이에서는 queue를 사용하므로 이과정이 O(1))

아래와 같은 BFS 풀이가 더 적절한 풀이라고 생각합니다.

import java.util.*;

class Solution {
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};

    public int solution(int[][] maps) {
        return bfs(maps);
    }

    public int bfs(int[][] maps) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 1});
        maps[0][0] = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int curX = current[0];
            int curY = current[1];
            int depth = current[2];
            if (curX == maps.length - 1 && curY == maps[0].length - 1) {
                return depth;
            }

            for (int i = 0; i < 4; i++) {
                int nextX = curX + dx[i];
                int nextY = curY + dy[i];

                if (nextX >= 0 && nextX < maps.length && nextY >= 0 && nextY < maps[0].length && maps[nextX][nextY] == 1) {
                    maps[nextX][nextY] = 0;
                    queue.add(new int[]{nextX, nextY, depth + 1});
                }
            }
        }
        return -1;
    }
}

실제 프로그래머스의 효율성 테스트 결과 역시 차이가 있음을 확인하였습니다.

1. 책에 기재된 다익스트라 풀이 코드
   

2. BFS 풀이
   

검토 부탁드리며, 혹시 저의 의견중 틀린 부분이 있으면 알려주시면 감사하겠습니다.