문제
N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
해결 방법
이 문제도 역시 다익스트라 알고리즘 문제이다. 문제를 보면 단방향 도로 라는 키워드와 최단 시간 이라는 키워드가 있는데, 이 두가지만 보아도 다익스트라 알고리즘 문제라는 것을 알아차릴 수 있다.
그리고 문제에서는 N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생을 구하는 것이기 때문에, 모든 학생들의 최단 경로를 구한 뒤에 그 값들을 비교해서 가장 큰 값을 출력하면 된다고 생각했다.
문제 발생
그러나 코딩 중 문제가 발생했다. 모든 학생들의 거리 테이블을 만들기 위해서 distance 라는 이름의 리스트를 사용했는데, 이차원 리스트로 선언을 하였는데 한 값만 바꾸어도 모든 값이 바뀐다.
INF = int(1e9)
inflist = [INF] * (n+1)
distance = []
for _ in range(n+1):
distance.append(inflist)
이렇게 선언했더니 distance[1][1] 값만 바꾸어도 distance[x][1] (여기서 x는 1이상 n이하) 값이 다 바뀌는 것이다. 선언을 비슷하고 다르게 해보아도 계속 이 문제가 발생하여 구글링을 해보았다.
얕은 복사
파이썬이 c언어와는 아예 달라서 이런일이 발생하는 것 같다. 쉽게 말하면 얕은 복사는 어떤 객체를 다른 객체에 복사하였을 때, 얕은 복사를 하게 되면 같은 주소값을 가지게 된다. a라는 객체를 b라는 객체로 복사 하였을 때, 같은 주소를 가지게 되면 b의 값을 변경하면 a의 값도 변경이 되는 거다. 이것은 심각한 코딩 오류를 야기할 수 있다.
즉, 위에서는 inflist 객체를 계속 추가했기 때문에, distance리스트 내에서 인덱스가 다르더라도, 같은 주소값을 갖게 되어 하나의 값만 변경해도 같은 주소값을 같는 객체들의 값이 다 변경이 되는 것이다.
그래서 아예 [INF] 리스트 자체를 바로 생성하는 코드로 바꾸었다.
최종 코드
import sys
import heapq
n, m, x = map(int,input().split())
INF = int(1e9)
graph = [[] for _ in range(n+1)]
# 1번부터 n번 학생까지.
distance = []
for _ in range(n+1):
distance.append([INF] * (n+1))
for _ in range(m):
s,e,ti = map(int,input().split())
graph[s].append((e,ti))
def dikjstra(start):
distance[start][start] = 0
q = []
heapq.heappush(q,(0,start)) # (거리, 도착점) 쌍
while q:
dist, now = heapq.heappop(q)
if distance[start][now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if distance[start][i[0]] > cost:
distance[start][i[0]] = cost
heapq.heappush(q,(cost,i[0]))
for i in range(1,n+1):
dikjstra(i)
longtime = 0
# 최대 시간 구하기
for i in range(1,n+1):
if longtime < distance[i][x] + distance[x][i]:
longtime = distance[i][x] + distance[x][i]
print(longtime)