Repository navigation
p.g. 490의 '풀이 1 다익스트라 알고리즘 구현' #3
Description
제가 가지고 있는 전자책은 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;
}
}
실제 프로그래머스의 효율성 테스트 결과 역시 차이가 있음을 확인하였습니다.
-
책에 기재된 다익스트라 풀이 코드
-
BFS 풀이
검토 부탁드리며, 혹시 저의 의견중 틀린 부분이 있으면 알려주시면 감사하겠습니다.
Activity