문제

Access

문제

백준이가 한 지점에서 출발을 해서 다시 처음 위치로 돌아갔을 때 시간이 되돌아 가는 경우가 있는 지 찾는 문제 입니다. 시간이 되돌아가는 간선이 있기 때문에 간선 값 중에 음수가 존재합니다 따라서 음수 간선까지 계산할 수 있는 벨만포드 알고리즘을 사용하는 것이 불가피해 보입니다. 그리고 시간이 이전보다 더 뒤로 가는 경우 를 확인하는 문제인데 이는 곧 순환하면 순환할 수록 간선의 값이 무한으로 줄어드는 음수 사이클 이 있는지 확인하는 문제가 됩니다

접근

제약 사항

그런데 문제에서는 시간이 뒤로 가는 경우를 판단할 때 백준이가 어디로부터 출발하는 지 명시가 안되어 있습니다. 즉, 출발 지점이 1번으로 고정되어 있는 것이 아닌 모든 지점에서 출발할 수 있기 때문에 모든 지점에서 벨만 포드를 돌려야 합니다. 그런데 벨만 포드는 한 지점에서만 돌려도 $O(V \cdot E)$

해결

보통 벨만 포드를 돌릴 때 최단 거리 배열을 선언한 다음, 시작 지점을 0으로 잡아놓고 나머지는 -1 또는 NULL 값으로 선언합니다. 그 이유는 다익스트라와 유사한데, 간선에서 두 정점 중 하나라도 방문이 되어야 누적 간선 값을 계산할 수 있기 때문입니다. 하지만 제약 사항에서도 설명되어 있듯이 모든 정점 갯수대로 벨만 포드를 돌렸다간 시간초과가 발생할 게 뻔합니다. 시간초과를 피하려면 모든 정점에서 동시에 시작하게 해야 하므로 최단 거리 배열을 전부 0으로 초기화 합니다. 이렇게 되면 어느 간선으로도 예외 없이 간선 값을 계산할 수 있어 시간도 단축시킬 수 있습니다.

알고리즘

이해를 좀더 쉽게 하기 위해 예제 입력1 의 두 가지 케이스를 예로 들어봅시다.

Case1 [음수 사이클 X]

Input (웜홀은 단방향, 노선은 양방향)

시작점	끝점	간선값
1	2	2
2	1	2
1	3	4
3	1	4
2	3	1
3	2	1
3	1	-3

Graph

1. 최단 거리 배열을 간선 갯수 + 1 길이에 0으로 초기화 합니다.

[0, 0, 0, 0]

2. 벨만 포드는 모든 간선을 정점 갯수 번 순회합니다. 이중 마지막 순회는 음수 사이클 여부를 최단 거리 갱신 여부로 판단합니다. 일단 모든 간선을 한 번 순회합니다 (2번 남음)

[0,-3,0,0]

3. 모든 최단 거리가 0이 되었기 때문에 일부 간선 값이 음수가 아닌 이상 최단거리 데이터는 갱신되지 않습니다. 여기서는 3번 -> 1번으로 가는 간선 값이 -3이기 때문에 1번 정점의 최단거리가 -3으로 업데이트 되었습니다.
4. 한번 더 같은 방식으로 간선을 순회합니다. (1번 남음)

[0,-3,-1,0]

5. 1번으로 이동하는 거리가 -3인 상태에서 2번으로 가는 거리 값을 구했는데 -3 + 2 = -1이 되었습니다. 그런데 이전의 2번 최단 거리가 0이였기 때문에 -1로 갱신되었습니다.
6. 마지막으로 간선을 순회합니다. 이번엔 최단거리가 갱신이 된다면 음수 사이클로 간주하게 됩니다.(0번 남음)

[0,-3,-1,0]

7. 어느 최단거리도 갱신이 되지 않았기 때문에 음수 사이클이 존재하지 않는 그래프로 판정되었습니다.

Case2 [음수 사이클 O]

Input (웜홀은 단방향, 노선은 양방향)

시작점	끝점	간선값
1	2	3
2	1	3
2	3	4
3	2	4
3	1	-8

Graph

1. Case1과 마찬가지로 배열을 초기화 합니다.

[0, 0, 0, 0]

2. 간선을 순회 합니다. (2번 남음), 이때 3 -> 1의 간선 값이 -8이므로 1번 정점의 최단 거리가 -8로 갱신이 됩니다.

[0, -8, 0, 0]

3. 간선을 다시 순회 합니다, (1번 남음), 1번 시점에서 2로 이동하는 값이 3이지만 1번의 최단 거리가 -8이기 때문에 3 - 8 = -5, 즉 2번 최단 거리가 -5가 되므로 갱신합니다. 3번도 마찬가지로 간선 값이 4 이지만 3번의 이전 정점인 -2의 최단 거리가 -5가 갱신되었으므로 -5 + 4 = -1 즉 -1로 갱신되었습니다. 마지막으로 1번의 정점도 이전 3번의 정점이 -1이 되었기 때문에 -8 + -1 = -9 즉 -9로 갱신되었습니다.

[0, -9, -5, -1]

4. 보시다시피 모든 정점이 갱신되었습니다. 최단 거리들이 죄다 음수가 되버리면 다음 순회, 앞으로도 순회할 때, 간선 값에 음수가 존재한다면 계속해서 갱신될 것입니다. 그런데 이미 3 -> 1로 가는 값이 -8이라서 마지막에서도 전부 갱신될 것 같습니다. 벨만 포드에서 간선 순회를 정점 갯수번으로 제한한 이유는 이런 음수 사이클의 무한 갱신을 막기 위함 입니다.

5. 마지막으로 순회합니다. 이젠 음수 사이클을 판정할 차례입니다. (0번 남음), 1 -> 2로 가는 간선 값은 3이지만 1번의 최단 거리는 -9이므로 이를 계산하면 값은 -6이 됩니다. 그런데 2의 최단 거리는 -5이므로 -6으로 갱신이 됩니다. 그 다음 2 -> 3을 확인할 때 간선 값은 4, 2번 까지의 최단 거리는 -6으로 갱신되었으므로 이를 계산하면 -2, 그러나 3번의 최단 거리 값은 -1이므로 3번 역시 갱신됩니다. 마지막으로 1 -> 3에서 간선 값은 -8이지만 3번의 최단 거리가 -2로 갱신되었으므로 계산하면 -10, -9였던 1의 최단거리보다 더 작으므로 -10으로 갱신이 됩니다. 결국 예상대로 전부 다 갱신이 되었습니다. 이거 순회 횟수 제한 없이 다른 조건으로 루프를 돌린다면 최단 거리는 계속해서 갱신될 것입니다. 이것을 음수 사이클 이라고 합니다. 하지만 횟수 제한을 걸었고 갱신이 되었다는 것을 알았기 때문에 음수 사이클로 판정합니다.

[0, -10, -6, -2]

코드

메인 코드

for _ in range(T):
    V, E, WE = map(int, input()[:-1].split())

    EDGES = []
    R = [0] * (V + 1)
    for _ in range(E):
        # 일반 노선 갖고오기
        u, v, w = map(int, input()[:-1].split())
        EDGES.append((u, v, w))
        EDGES.append((v, u, w))
    for _ in range(WE):
        # 웜홀
        u, v, w = map(int, input()[:-1].split())
        EDGES.append((u, v, -w))
    
    if process(V, E*2+WE, EDGES, R):
        # 시간이 줄어듦
        result.append("YES")
    else:
        result.append("NO")
print('\n'.join(result))

전부 동시에 계산하기 위해 간선 배열을 INF나 None이 아닌 0으로 초기화 합니다.

R = [0] * (V + 1)

알고리즘 코드

def process(V, E, edges, weights):
    def bfs():
        for i in range(V):
            for j in range(E):
                u, v, w = edges[j]
                if weights[v] > weights[u] + w:
                    weights[v] = weights[u] + w
                    if i == V - 1:
                        return True
        return False
    is_cycle = bfs()
    if is_cycle:
        return True
    else:
        return False

정점 갯수 V, 간선 갯수 E, 정점과 간선 edges, weights를 인자값으로 받고 음수 사이클 여부를 리턴합니다.

모든 간선을 정점 갯수 번 순회합니다.

for i in range(V):
    for j in range(E):

간선 튜플(또는 리스트)로부터 시작 지점 u, 끝 지점 v, 그리고 간선 값 w을 갖고옵니다.

u, v, w = edges[j]

if weights[v] > weights[u] + w:
    weights[v] = weights[u] + w
    if i == V - 1:
        return True

u의 최단 거리와 v로 향하는 간선 값 w을 더한 값을 기존의 v의 최단 거리와 비교해 더 작으면 갱신합니다. 단 마지막 순회때 갱신이 이루어지게 된다면 음수 사이클이므로 True를 리턴합니다. 그렇지 않고 for문을 빠져나오면 False를 리턴합니다.

후기

이 문제를 풀었을 당시, 벨만포드 알고리즘을 막 공부하고 타임머신 문제를 푼 다음, 이 문제를 풀게 되었는데, 벨만포드 알고리즘의 원리를 더 자세히 배울 수 있는 기회가 되었습니다. 특히 음수 사이클의 원리를 잘 몰랐는데 이 문제를 통해 정확하게 알게 되었습니다. 혹시 저처럼 벨만포드 알고리즘을 공부하고 계시는 분이라면 이 문제를 추천합니다.