백준 11657 타임머신 문제풀이

문제 

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

11657번: 타임머신

 

 

문제 접근 방식

단일 노드에서 모든 노드로의 최단 경로의 길이를 구하는 문제이며, 간선간의 음의 가중치가 존재한다. 

가중치 그래프  +단일 노드 + 음의 간선이 존재 이기 때문에 벨만 포드 알고리즘을 활용하여 문제를 풀었다.

 

벨만 포드에 대한 내용을 짧게 정리를 해보자면 아래와 같다.

1. s(시작노드)로 부터 i 개의 간선 만큼 떨어져있는 노드까지의 최단 경로 길이를 저장하는 dist라는 배열을 선언한다.

dist[v] = s(시작노드)로 부터 i 개의 간선 만큼 떨어져있는 노드 v 까지의 최단 경로 길이

 

2. 간선의 길이를 하나씩 늘려가면서 V-1 개의 간선만큼 떨어져 있을 때의 dist를 구한다.

        2.1. V-1번 까지 구하는 이유 > 모든 노드 V를 사용하여 하나로 이었을 때, 간선의 수는 V-1 개 이기 때문이다.

        2.2. dist 갱신(아래 1,2번 비교하여 작은 값으로 갱신)

            1. 경유지 u 를 거쳐 v 로 가는 최단 길이 = dist [ u ] + w           (w = u > v 길이)
            2. 지금까지 구한 s > v 로의 최단 경로 길이 = dist [ v ]

dist[v]=min(dist[u]+w ,dist[v])

 

3. 음의 사이클을 확인하기 위해 한 번더 dist를 갱신해서 값이 작아진 경우를 확인한다.

 

더 자세한 설명은 코드와 주석을 보면서 이해해보자

 

 

시간 복잡도

[노드 수-1] 만큼 순회해야하기 때문에 O(V) 가 걸리고, 순회할 때 마다 모든 간선을 확인해야 하므로 각 순회마다 O(E)가 소요된다. 전체적인 소요 시간은 O(V * E) 가 되고, V<=500, E<=6000 이므로 시간 내에 동작함을 알 수 있다.

 

 

코드

코드(주석  O)

INF=int(1e9)

def bellman_ford():
    dist = [INF for _ in range(n + 1)]
    dist[1] = 0

    # 노드의 수 V -1 만큼 순회
    # s > 특정 노드 까지 사용되는 간선의 수 = i
    for i in range(1,n):

        # i개의 간선을 활용하여, u 노드를 거쳐서 v 노드로 가는 최단 경로의 길이(dist[v])를 갱신하기 위한 과정
        for u, v, w in edges:

            # 만약 s 와 u 가 이어져 있지 않다면 pass 한다.
            if dist[u] == INF:
                continue

            # 아래 1,2를 비교하여 작은 값으로 갱신한다
            # 1. s > u 로 가는 최단 경로( dist[u] ) + u>v 길이(w)
            # 2. 지금까지 구한 s > v 로의 최단 경로 길이
            dist[v] = min(dist[v], dist[u] + w)

    # 음수 사이클 판정
    # 마지막으로 한번 더 간선을 순회 > 값이 줄어들고 있다면 음수 사이클이 존재한다고 판정
    for u, v, w in edges:
        if dist[u] != INF and dist[v] > dist[u] + w:
            return -1

    return dist

if __name__=='__main__':
    global n,m,edges
    n,m=map(int,input().split())
    edges=[tuple(map(int,input().split())) for _ in range(m)]

    # Bellman-Ford를 활용하여 dist 반환
    dist=bellman_ford()


    # 주어진 조건에 맞게 출력
    answer=''
    if dist !=-1:
        for i in range(2,n+1):
            answer+= str(dist[i]) if dist[i] !=INF else str(-1)
            answer+='\n'
    else:
        answer='-1'

    print(answer)

 

 

코드(주석 X)

INF=int(1e9)

def bellman_ford():
    dist = [INF for _ in range(n + 1)]
    dist[1] = 0

    for i in range(1,n):
        for u, v, w in edges:
            if dist[u] == INF:
            	continue
            dist[v] = min(dist[v], dist[u] + w)

    # 음수 사이클 판정
    for u, v, w in edges:
        if dist[u] != INF and dist[v] > dist[u] + w:
            return -1

    return dist

if __name__=='__main__':
    global n,m,edges
    n,m=map(int,input().split())
    edges=[tuple(map(int,input().split())) for _ in range(m)]

    # Bellman-Ford를 활용하여 dist 반환
    dist=bellman_ford()


    # 주어진 조건에 맞게 출력
    answer=''
    if dist !=-1:
        for i in range(2,n+1):
            answer+= str(dist[i]) if dist[i] !=INF else str(-1)
            answer+='\n'
    else:
        answer='-1'

    print(answer)

 

회고

 

** 노드 s 로부터 간선 i 개 거리의 노드 v에 대해 어떻게 순회를 하여 처리하는지 배울 수 있었다.

1. 간선의 수 만큼 반복

2. 모든 간선을 순회하며, 이어져 있지 않은 경우는 pass

 

**음의 사이클을 어떻게 판정하는지 배울 수 있었다.

모든 노드를 최대로 이었을 경우 최대 간선 수(V-1) 에서 한 번더 사이클을 돌려서 값을 비교

** 노드 s 로부터 간선 i 개 거리의 노드 v에 대해 어떻게 순회를 하여 처리하는지 배울 수 있었다.
1. 간선의 수 만큼 반복
2. 모든 간선을 순회하며, 이어져 있지 않은 경우는 pass



** 음의 사이클을 어떻게 판정하는지 배울 수 있었다.
모든 노드를 최대로 이었을 경우 최대 간선 수(V-1) 에서 한 번더 사이클을 돌려서 값을 비교