[BOJ 1865][백준 1865번] 웜홀 (파이썬 풀이)

https://www.acmicpc.net/problem/1865

 

 

🤔 문제 설명 및 입출력

---

 

✍ 접근 방법

---

 

음수 가중치가 들어가는 그래프 탐색 문제이다 ➡ 벨만-포드 알고리즘을 적용해서 풀자.

 

사실 이렇게 알고리즘을 뭔가 공식화해서 풀어재끼는게 썩 유쾌하지는 않지만, 그래도 코딩 테스트를 염두해보았을 때,머리 속을 스쳐지나가는 생각들을 단숨에 훅 잡아채는게 유리하다는 생각이 든다.

 

하지만, 이 문제는 시작점에서 도착점까지의 최소 경로비용을 구하는 순수 벨만-포드 문제가 아니다. 문제의 요지는 백준이가 시간이 줄어들면서, 출발 위치로 돌아오는 것이 가능한지를 물어보기 때문에, 우리는 주어진 그래프에서 벨만-포드 알고리즘이 무한히 반복되는 경우 ( 음수 사이클에 빠지는 경우)를 찾아야한다.

 

그럼 그 음수 사이클을 어떻게 찾냐??

노드의 갯수가 N개라고 하면, 벨만 포드 알고리즘은 N-1번의 순환 이내에 최적화된 경로를 반드시 뱉어낸다. 그렇다면, 알고리즘이 N-1번을 넘어 N번째의 순환에 돌입한다면, 이건 뭔가 하자가 있는 (음수 사이클이 있는) 케이스라고 생각할 수 있다.

 

우리는 이 점에 착안하여, 문제 풀이를 하면 된다.

 

 

 

 

👨‍💻 소스 코드

---

• 파이썬

# INF = float('inf')로 지정하면, 도로 없이 웜홀만 존재하는 그래프에서
# dis[goal] > dis[cur] + weight을 정확히 처리하지 못한다.
# 무한대 > 무한대 - T 꼴이 되어버려서, 분명 음의 사이클이 존재하는데, 없는 것으로 간주한다


# 그래서 거리 가중치를 초기화할때 사용할 변수인 INF는 문제 견적보고 적당히 큰 수로 만들어야한다
INF = 0xffffff

def bf(i:int):
    # i --> 시작 지점
    dis = [INF] * (N+1)
    dis[i] = 0 # 시작위치의 거리 가중치 초기화
    
    # 뺑뺑이 있는지 찾기 위해서 N번 반복
    for cnt in range(N):
        for edge in edges:
            cur = edge[0]
            goal = edge[1]
            weight = edge[2]
            if dis[goal] > dis[cur] + weight:
                dis[goal] = dis[cur] + weight

                # 음의 사이클 존재
                if cnt == N-1:
                    return True
    #음수 사이클 없음
    return False




TC = int(input())

for tc in range(TC):
    N,M,W = map(int,input().split())
    # 그래프 인접 리스트
    edges = []
    # 도로 그래프 입력
    for _ in range(M):
        S,E,T = map(int,input().split())
        edges.append([S,E,T])
        edges.append([E,S,T])
    #웜홀 정보 입력
    for _ in range(W):
        S,E,T = map(int,input().split())
        edges.append([S,E,-T])

    negative_cycle_exist = bf(1)
    # 음수 사이클이 존재하는지를 확인하는 것
    print('YES' if negative_cycle_exist else 'NO') 

 

주석에 적어놓았듯, INF 값을 셋팅하는 것이 이번 문제의 의외의 복병이였다. 나는 이런 그래프 문제를 풀 적에는 가중치 초기값을 float('inf')로 초기화 하는데, 이번에는 그게 큰 버그의 원인이 되었다.

 

무한의 값이 되어버린 INF는 도로와 이어지지 않고 웜홀만 존재하는 경우, dis[cur] - weight 를 계속해서 INF로 유지하여, 음의 사이클이 존재한다고 인지하지 못했다.

 

이 에러 잡겠다고 꽤 많은 시간을 고민했던 만큼, 다음에 유사한 문제를 풀 적에는 이런 예외도 있었다는 것을 기억해야겠다.

 

그리고 또 하나 짚고 넘어가야할 것은, 이번 문제는 따로 시작 위치가 주어지지 않았다.

사실 시작 위치와 끝 위치로 경로 최소값을 구하는 문제가 아니니까 그런거 같은데, 음수 사이클의 존재 여부만을 살피기 위해서라면 시작 위치는 아무렇게나 설정해도 된다. 즉, negative_cycle_exist = bf(1)에서의 1을 다른 숫자로 바꿔도 문제가 없다는 뜻이다.

 

 

🔥 강평

---

밸만-포드 알고리즘 자체는 다익스트라보다 구현이 쉬운 편이라 구현상의 어려움은 크게 없었던것 같다. 다만, 이 알고리즘을 어떻게 사용할지에 대한 고민이 깊었던 문제이다. 항상 느끼는 것이지만, 이런 그래프 류 문제는 진짜 반복만이 생명인것 같다. 비슷한 문제를 많이 풀어봐야겠다.