• 문제 : 백준 1865번 웜홀

• 틀린 풀이 : 플로이드-와샬 알고리즘

• 틀린 이유 : 음수 사이클?

• 맞은 풀이 : 벨만-포드 알고리즘

• 설명

  • 모든 노드에 대해 거리를 계산할 필요 없음
  • 음수 사이클이 존재하면 무조건 가능

• 풀이

  1. 연결리스트 set
  2. 1번에서 출발한다고 가정
  3. 모든 에지를 돌면서 relax
     • 거리리스트[도착지] = min(거리리스트[도착지], 거리리스트[출발지] + 시간)
  4. 노드 개수만큼 반복
  5. 거리리스트를 돌면서 현재 최단 거리보다 시간을 더했을 때 더 작아지는 경우 return True (음수사이클)

• 후기

  • 왜 거리 리스트를 무한대로 초기화하면 안되는지 모르겠다
  • 벨만-포드 알고리즘에 대해 정확히 이해하자
  • 다익스트라, 플로이드-와샬과의 차이에 대해 공부하자

• 출처 : https://www.acmicpc.net/problem/1865

틀린 코드

# 음수 사이클?
import sys


def get_dist_list(v, edge_list):
    dist_list = [[float('inf') for _ in range(v+1)] for _ in range(v+1)]
    for s, e, w in edge_list:
        dist_list[s][e] = w
    for k in range(1, v+1):
        for i in range(1, v+1):
            for j in range(1, v+1):
                dist_list[i][j] = min(dist_list[i][j], dist_list[i][k]+dist_list[k][j])
                pass
    return dist_list


tc = int(sys.stdin.readline().rstrip())
for _ in range(tc):
    v, e1, e2 = map(int, sys.stdin.readline().rstrip().split(' '))
    edge_list = []
    for i in range(e1):
        s, e, t = map(int, sys.stdin.readline().rstrip().split(' '))
        edge_list.append((s,e,t))
        edge_list.append((e,s,t))
    for i in range(e2):
        s, e, t = map(int, sys.stdin.readline().rstrip().split(' '))
        edge_list.append((s,e,-t))
    dist_list = get_dist_list(v, edge_list)
    possible = False
    for i in range(1, v+1):
        if dist_list[i][i] < 0:
            possible = True
            break
    if possible:
        print('YES')
    else:
        print('NO')
pass

맞은 코드

import sys


def 초기화():
    지점개수, 도로개수, 웜홀개수 =  map(int, sys.stdin.readline().split())
    연결리스트 = []
    for _ in range(도로개수):
        출발지, 도착지, 시간 =  map(int, sys.stdin.readline().split(' '))
        연결리스트.append((출발지, 도착지, 시간))
        연결리스트.append((도착지, 출발지, 시간))
    for _ in range(웜홀개수):
        출발지, 도착지, 시간 =  map(int, sys.stdin.readline().split())
        연결리스트.append((출발지, 도착지, -시간))
    return 지점개수, 도로개수, 웜홀개수, 연결리스트


def 음수사이클(지점개수, 연결리스트):
    # float('inf')로 초기화하면 틀림
    거리리스트 = [999999 for _ in range(지점개수+1)]
    거리리스트[1] = 0
    for _ in range(지점개수):
        for 출발지, 도착지, 시간 in 연결리스트:
            거리리스트[도착지] = min(거리리스트[도착지], 거리리스트[출발지] + 시간)
    for 출발지, 도착지, 시간 in 연결리스트:
        if 거리리스트[도착지] > 거리리스트[출발지] + 시간:
            return True
    return False
        

테스트케이스 = int(sys.stdin.readline())
for _ in range(테스트케이스):
    지점개수, 도로개수, 웜홀개수, 연결리스트 = 초기화()
    if 음수사이클(지점개수, 연결리스트):
        print('YES')
    else:
        print('NO')