문제
때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 개의 지점이 있고 N개의 지점 사이에는 개의 도로와 개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.
시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.
접근 방식
웜홀이 음수 가중치를 갖기 때문에, 그래프 내 음수 사이클 존재 여부를 확인하는 문제로 해석할 수 있다.
따라서, 벨만-포드 알고리즘을 적용하는 방향으로 접근하였다.
def solution(n: int, edges: list) -> bool:
dist = [float("inf")] * (n + 1)
dist[1] = 0
for i in range(1, n + 1):
for s, e, cost in edges:
if dist[s] != float("inf") and dist[e] > dist[s] + cost:
dist[e] = dist[s] + cost
if i == n: return True
return False위는 일반적인 벨만-포드 알고리즘 구현 방식이다. n번 반복한 뒤, 마지막 반복에서 거리 갱신이 일어나면 음수 사이클이 존재하는 것이므로 True를 리턴하고, 그렇지 않다면 False를 리턴해 출발하였을 때보다 시간이 되돌아가 있는 경우가 있는지를 확인할 수 있다.
주의해야 할 점
여기서 중요하게 짚고 넘어가야 하는 부분이 있다.
1. 백준이가 출발을 어디서 하는가?
백준이는 아무데서나 출발할 수 있다. 따라서 음수 가중치가 존재하기만 한다면, 출발했을 때보다 시간이 되돌아가 있는 경우가 있다는 의미이다.
2. 출발 지점을 어디로 설정해야 하는가?
모든 지점이 연결되어 있다면, 시작 지점이 1이어도 상관없지만(어차피 모든 지점을 모두 지나가게 됨), 1 지점과 연결되어 있지 않은 지점이 존재한다면, 해당 지점들 사이에서 음수 사이클이 발생하는지 확인할 수 없기 때문이다.
이 문제를 해결하기 위해 0이라는 가상 지점을 만든 후 모든 지점과 연결만 시켜준다면, 기존 알고리즘으로도 무리 없이 음수 사이클을 발견할 수 있다.
혹은 if문의 dist[s] != float("inf") 부분을 제거하여 방문하지 않은 노드더라도 일단 탐색을 하는 방식이 있다.
코드 1(가상 지점 만들기)
def solution(n: int, edges: list) -> bool:
new_edges = edges + [(0, i, 0) for i in range(1, n + 1)]
dist = [float("inf")] * (n + 1)
dist[0] = 0
for i in range(n + 1):
for s, e, cost in new_edges:
if dist[s] != float("inf") and dist[e] > dist[s] + cost:
dist[e] = dist[s] + cost
if i == n: return True
return False0과 모든 지점간 비용이 0으로 연결되어있는 간선을 만든 후, 시작 지점을 0으로 둔다.
이후 n번 반복한 다음, 마지막 반복에서 갱신이 일어나면 음수 사이클이 있는것이므로 True를 리턴한다.
코드 2(방문 여부 체크 X)
def solution(n: int, edges: list) -> bool:
dist = [100_000_000] * (n + 1)
dist[1] = 0
for i in range(n + 1):
for s, e, cost in edges:
if dist[e] > dist[s] + cost:
dist[e] = dist[s] + cost
if i == n: return True
return False위 코드에서는 시작 지점을 1로 설정해주었지만, 시작 지점을 설정해주지 않아도 되고, 모든 지점에서 동시에 출발해도 상관 없다(dist 리스트의 모든 값을 0으로 초기화해도 상관 없음).
위 방식에서 중요한 점은 절대 dist 리스트를 float("inf")로 초기화하면 안된다는 점인데, 무한에 음수를 더해도 여전히 무한이기 때문에 거리 갱신이 이루어지지 않기 때문이다.
그럼에도 불구하고 내가 틀린 이유
두 가지 방식을 모두 적용해보았지만 2%에서 계속 틀려서 다른 사람들의 코드를 참고했다. 하지만 내 코드와의 차이점을 찾을 수 없었다..
그 해답을 질문 게시판에서 찾을 수 있었다.
그동안 도로의 간선도 웜홀과 동일하게 방향 그래프로 넣어주었다.. 즉, solution() 함수에 문제가 있는게 아니라 그래프 자체에 문제가 있었던 것이다.
# 원래 이렇게 넣어주고 있었음
edges.append(tuple(map(int, input().split())))# 도로는 무방향 -> 양쪽 모두 추가해야 함
s, e, c = map(int, input().split())
edges.append((s, e, c))
edges.append((e, s, c))바꿔주니까 잘 작동하는 것을 확인할 수 있었다..
이 문제는 최단 거리를 묻는 문제가 아니라서, 벨만 포드 외에도 다양한 풀이법이 존재하는 것 같다. 나중에 다른 방법도 시도해보는게 좋을 것 같다.
