매일 문제 풀이

1. 웜홀(백준 1865번)

주어진 그래프에서 비용이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력하는 문제.
비용이 줄어든다는 것은 결국 음수 비용이라는 말이고,
출발 위치로 돌아오는 것이 가능하다는 것은 그 경로를 반복할 수 있다는 것, 즉 음수 사이클의 존재를 의미한다.
정리하면 주어진 그래프에서 음수 사이클이 존재하는지를 찾는 문제이다.

def main() -> None:
    def argmin(dist, visited)-> int:
        shortest = -1
        arg = 0
        for i in range(1, N+1):
            if not visited[i] and dist[i] != -1:
                if shortest == -1 or dist[i] < shortest:
                    shortest = dist[i]
                    arg = i
                
        return arg
    
    def dijkstra(start, end) -> int:
        if (start, end) in cache:
            return cache[(start, end)]

        dist_shortest = [-1 for _ in range(N+1)]
        visited = [False for _ in range(N+1)]
        cur = start
        visited[cur] = True
        dist_shortest[cur] = 0
        while not visited[end]:
            for node, time in roads[cur].items():
                new_dist = dist_shortest[cur]+time
                if dist_shortest[node] == -1 or new_dist < dist_shortest[node]:
                    dist_shortest[node] = new_dist

            visited[cur] = True
            cache[(start, cur)] = dist_shortest[cur]
            if not (cur := argmin(dist_shortest, visited)): break

        return dist_shortest[end]
    
    TC = int(input())

    for _ in range(TC):
        N, M, W = map(int, input().split())

        flag = False
        cache = {}
        roads = {i: {} for i in range(1, N+1)}
        for _ in range(M):
            s, e, t = map(int, input().split())
            roads[s][e] = t
            roads[e][s] = t

        for _ in range(W):
            s, e, t = map(int, input().split())
            time = dijkstra(e, s)
            if time != -1 and t > time:
                flag = True
                break

        if flag:
            print("YES")
        else:
            print("NO")

main()

처음에는 웜홀이 하나인 경우만 가정하여
웜홀의 출구에서 입구로 오는 시간이 웜홀로 감소되는 시간보다 작으면 YES를 출력하도록 하였다.
하지만 중간 경로에서 다른 웜홀을 이용하는 경우가 있어서 웜홀이 여러 개인 경우에는 오답을 출력할 가능성이 있다.

def main() -> None:
    INF = 25000001
    def BF() -> bool:
        shortest = [INF for _ in range(N+1)]
        
        shortest[roads[0][0]] = 0
        for _ in range(N):
            for s, e, t in roads:
                if shortest[s] + t < shortest[e]:
                    shortest[e] = shortest[s] + t

        for s, e, t in roads:
            if shortest[s] + t < shortest[e]:
                return True

        return False
    
    TC = int(input())

    for _ in range(TC):
        N, M, W = map(int, input().split())

        roads = []
        for _ in range(M):
            s, e, t = map(int, input().split())
            roads.append((s, e, t))
            roads.append((e, s, t))

        for _ in range(W):
            s, e, t = map(int, input().split())
            roads.append((s, e, -t))

        if BF():
            print("YES")
        else:
            print("NO")

main()

이 경우에는 벨만-포드 알고리즘을 찾아서 그래프에 최소 하나 이상의 음수 사이클이 존재하는지를 확인하면 된다.

또한 특정 노드에 최초로 방문하는 때에 웜홀(음수 비용인 간선)을 이용하는 경우가 있으므로
INF - (웜홀로 감소하는 시간) < INF 가 참이 되는 조건문을 사용해야 한다.
현재 노드까지의 비용 != INF 조건을 추가하거나
부동소수점의 inf를 사용하게 되면 답을 찾지 못 하는 경우가 발생할 수 있다.

네트워크 공부

다음 TIL에 합쳐서 올릴 예정