녹색 옷 입은 애가 젤다지?
요즘 그래프이론을 꽤나 열심히 풀고 있어서 오늘의 그래프로 다익스트라 문제를 건드려 보았다. 최근에 사내 역량 인증 시험에 응시했었는데 하도 자료구조를 리스트로 대체해서 쓰다보니깐 덱이 리스트 대비 어떤 장점이 있는지 기억이 안나서 테케 몇 개를 틀려서 아쉽게 만점을 받지 못하였다. 그래서 자료구조 연습도 할 겸 해서 다익스트라 문제를 꺼내왔다. 언제나 그랬듯이 별 생각없이 리스트로 먼저 구현했었다. 아래와 같이 BFS와 유사하지만 visited에 숫자를 도입해서 구현하였다.
import sys
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
cnt = 1
while True:
arr = []
visited = []
N = int(sys.stdin.readline())
if N == 0:
break
for i in range(N):
arr.append(list(map(int, sys.stdin.readline().split())))
visited.append([float('inf')] * N)
q = [[0, 0]]
visited[0][0] = arr[0][0]
while q:
x, y = q.pop()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
cost = visited[x][y] + arr[nx][ny]
if cost < visited[nx][ny]:
visited[nx][ny] = cost
q.append([nx, ny])
print(f"Problem {cnt}: {visited[-1][-1]}")
cnt += 1
결과적으로 이 코드는 시간 초과가 났다. 사실 뭐 얼마나 단축되는지는 잘 모르겠긴 한데 heapq를 사용하면 그래도 최솟값 먼저 뽑으니 뭐라도 단축되겠지 하는 생각으로 도입했다. 아래는 내가 아닌 챗봇의 나의 고민에 대한 대답이다. 틀린게 있다면 얘기해주시면 좋겠다.
우선순위 큐를 사용하면 가장 비용이 낮은 노드를 먼저 방문하게 되어 그래프를 더 효율적으로 탐색할 수 있습니다.
일반적으로 대부분의 그래프 탐색 알고리즘(DFS, BFS 등)의 경우에는 모든 노드를 방문해야 하므로 최악의 경우 시간 복잡도는 O(V + E)입니다. 여기서 V는 그래프의 노드 수, E는 에지의 수입니다.
그러나 우선순위 큐를 사용하는 알고리즘인 다익스트라 알고리즘의 경우, 각 노드는 한 번만 큐에 들어가므로 큐에 노드를 입력하거나 제거하는데 드는 시간 복잡도가 O(logV)입니다. 따라서 다익스트라 알고리즘의 총 시간 복잡도는 O((V+E) logV)가 됩니다.
그럼에도 불구하고, 이러한 로직 변경은 기존의 DFS 알고리즘이 동일한 노드를 여러 번 방문하거나 큐에 넣는 경우, 특히 그래프가 밀집해 있어서 모든 노드와 에지를 방문해야 하는 경우에 시간 복잡도를 크게 개선할 수 있습니다. 이런 상황에서는 다익스트라 알고리즘이 더 효율적입니다.
뭐 그렇다고 한다. 나는 이정도로 세밀한 거를 아는게 그리 즐겁진 않아서 대충 이러면 이거써야지 정도만 알고 넘어가는 편인데 이러면 손해보기 쉬운데 읽으시는 분들은 더 꼼꼼하게 보시길 바랍니다. 아래는 정해 코드입니다.
import sys , heapq
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
cnt = 1
while True:
arr = []
visited = []
N = int(sys.stdin.readline())
if N == 0:
break
for i in range(N):
arr.append(list(map(int, sys.stdin.readline().split())))
visited.append([float('inf')] * N)
q = [[arr[0][0], 0, 0]]
visited[0][0] = arr[0][0]
while q:
cost, x, y = heapq.heappop(q)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
next_cost = cost + arr[nx][ny]
if next_cost < visited[nx][ny]:
visited[nx][ny] = next_cost
q.append([next_cost, nx, ny])
print(f"Problem {cnt}: {visited[-1][-1]}")
cnt += 1