풀이 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
from heapq import heappush, heappop
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
round = 0
while True:
n = int(input())
round += 1
if n == 0:
break
data = []
for _ in range(n):
data.append(list(map(int, input().split())))
visited = [[False for _ in range(n)] for _ in range(n)]
visited[0][0] = True
q = []
heappush(q, (data[0][0], 0, 0))
while q:
dis, x, y = heappop(q)
if x == n - 1 and y == n - 1:
print("Problem {0}: {1}".format(round, dis))
break
if data[x][y] < dis:
continue
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == False:
data[nx][ny] += dis
visited[nx][ny] = True
heappush(q, (data[nx][ny], nx, ny))
|
cs |
처음 제출시, 틀렸던 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
from heapq import heappush, heappop
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
round = 0
while True:
n = int(input())
round += 1
if n == 0:
break
data = []
for _ in range(n):
data.append(list(map(int, input().split())))
result_data = copy.deepcopy(data)
q = []
heappush(q, (data[0][0], 0, 0))
while q:
dis, x, y = heappop(q)
if x == n - 1 and y == n - 1:
print("Problem {0}: {1}".format(round, dis))
break
if data[x][y] < dis:
continue
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
data[nx][ny] += dis
heappush(q, (data[nx][ny], nx, ny))
|
cs |
틀렸던 이유
visited로 방문 체크를 해주지 않아서 시간 초과가 나고 말았다.
처음에 visited로 방문 체크를 하지 않았던 것은 실수가 아니라, 체크를 해주면 오답이 날거란 생각 때문이다.
Why?
Q1. 체크를 해주면 오답이 날거란 생각 때문이다. -> 왜 그렇게 생각했지?
기존의 bfs 최단 거리 문제와 달리, 가중치가 있기 때문에 a -> b로 가는 최단 거리가 어떤 것을 거쳐가느냐에 따라 다를 것이라고 생각했다.
0, 0에서 0, 2까지 가는 최단거리는 2이지만, 4를 거친 과정을 visited에 저장해버리면 1->0->1->5를 거친 최단 경로가 저장이 되지 않을 것만 같았다.
하지만 이러한 생각은 dis를 우선 순위로 두어 pop하기 때문에, 가장 짧은 경로로 먼저 초기화가 되서 visited로 방문처리를 해도 별 문제가 없게 된다. -> 왜 이렇게 되지?
Q2. 왜 dis를 우선 순위로 두어 pop을 하면 각 지점까지 도달하는 경로 중, 최단 거리를 보장하는 거지?
어느 한 지점까지의 경우만이 아니라, 가장 짧은 거리를 제일 우선으로 pop하기 때문에, 모든 지점까지의 최단 거리가 계산된다.