[백준] 11657. 타임머신 (파이썬)

🗂️   문제 

11657. 타임머신

---

 

 

---

📌   Point

Bellman-Ford Algorithm

벨만-포드 알고리즘은 단일 출발점 최단 경로(SSSP, Single Source Shortest Path)를 구하는 알고리즘

• 다익스트라와 달리 음의 가중치를 포함한 그래프에서도 사용 가능.

 

기본 코드

def bellman_ford(V, edges, start):
    # 거리 배열 초기화 (무한대)
    INF = float('inf')
    dist = [INF] * V
    dist[start] = 0  # 시작 정점 거리 = 0

    # (V-1)번 모든 간선 확인
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:  
                dist[v] = dist[u] + w  

    # 음수 사이클 확인
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return "Negative Cycle Detected"

    return dist

# 예제 그래프 (정점 5개, 간선 6개)
V = 5
edges = [
    (0, 1, 4),
    (0, 2, 5),
    (1, 2, -2),
    (1, 3, 6),
    (2, 3, 1),
    (3, 4, -3)
]

start = 0
print(bellman_ford(V, edges, start))

# 결과
[0, 4, 2, 3, 0]

 

 

---

📄   코드

def bellman(V, edges, start):
    INF = float('inf')  # 무한대 값을 설정하여 초기 거리 값으로 사용
    dist = [INF] * (V+1)  # 모든 정점의 거리를 무한대로 초기화
    dist[start] = 0  # 시작 정점의 거리는 0으로 설정

    # 벨만-포드 알고리즘 수행 (V번 반복)
    for _ in range(V):  
        for u, v, w in edges:  # 모든 간선(u → v, 가중치 w)에 대해 업데이트 시도
            if dist[u] != INF and dist[u] + w < dist[v]:  
                dist[v] = dist[u] + w  # 더 짧은 경로가 발견되면 거리 갱신

    # 음의 사이클 존재 여부 확인
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:  
            return -1  # 음의 사이클이 존재하면 -1 반환

    # 도달할 수 없는 정점의 거리 값을 -1로 변경
    for i in range(V+1):
        if dist[i] == INF:
            dist[i] = -1

    return dist  # 최단 거리 배열 반환

def main():
    N, M = map(int, input().split())  # 정점 수 N, 간선 수 M 입력
    edges = [tuple(map(int, input().split())) for _ in range(M)]  # 간선 정보를 리스트로 저장
    start = 1  # 시작 정점을 1번으로 고정
    dist = bellman(N, edges, start)  # 벨만-포드 알고리즘 실행

    if dist == -1:
        print(dist)  # 음의 사이클이 존재하면 -1 출력
    else:
        print(*dist[2:], sep='\n')  # 2번 정점부터 출력 (1번 제외)

if __name__ == "__main__":
    main()

 

 

 

---

✍🏻   풀이

시간 복잡도 : O(VM)

 

1. 초기화
   • dist 배열을 생성하여 모든 정점의 최다 거리를 INF(무한대)로 설정한다.
   • 시작 정점의 거리를 0으로 설정한다. (dist[start] = 0)
2. V번 반복하여 거리 갱신
   • 모든 간선을 확인하며, 기존 거리보다 더 짧은 경로가 발견되면 거리를 갱신한다.
   • 최단 경로는 최대 V번 반복하면 보장된다. (for _ in range(V))
3. 해당 도시로 가는 경로가 없는 경우 확인
   • edges를 한 번 더 돌면서, dist[u] + w < dist[v]가 성립하면 음의 사이클이 존재하는 것이다.
   • 모든 정점이 무한히 감소할 수 있으므로 -1을 반환한다.
     • (문제에서 다음 부분에 해당)
     • 만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다.
4. 도달할 수 없는 정점 처리
   • 최단 경로를 찾지 못한 정점은 -1로 변환한다.
5. 결과 반환
   
   • dist = -1이면, -1을 반환한다.
   • dist != -1이면, 2번 도시부터 최단 경로(dist[i])를 반환한다.