파이썬 코딩테스트 강좌, 플로이드-워셜

안녕하세요! 이번 강좌에서는 플로이드-워셜(Floyd-Warshall) 알고리즘에 대해 깊이 있게 알아보겠습니다. 이 알고리즘은 주어진 그래프의 모든 쌍 최단 경로를 찾는 문제를 해결하는 데 매우 유용합니다. 우리는 이 알고리즘을 이해하기 위해 예제를 통해 설명하고, 최적화를 포함하여 다양한 변형도 논의할 것입니다.

플로이드-워셜 알고리즘이란?

플로이드-워셜 알고리즘은 그래프 이론에서 모든 노드 간의 최단 경로를 찾는 데 사용되는 알고리즘입니다. 이 알고리즘은 다음과 같은 과정을 통해 작동합니다.

그래프의 각 정점 쌍에 대해 초기 거리 값을 설정합니다.
각 정점을 시작 정점으로 간주하여 최단 거리를 업데이트합니다.
거리 행렬을 반복적으로 업데이트하여 최종적으로 모든 쌍의 최단 거리를 찾습니다.

문제 설명

그럼 이제 문제를 살펴보겠습니다. 다음과 같은 그래프가 주어졌다고 가정합시다.

        노드: 0, 1, 2
        엣지: 
        0 -> 1 (거리 3)
        0 -> 2 (거리 8)
        1 -> 2 (거리 2)

입력

그래프의 노드 수와 각 엣지의 거리 정보가 주어집니다. 아래와 같은 형식으로 입력을 받습니다:

출력

각 노드 간의 최단 거리 행렬을 출력합니다.

알고리즘 구현

이제 플로이드-워셜 알고리즘을 파이썬으로 구현해 보겠습니다. 아래는 알고리즘의 코드입니다:

def floyd_warshall(num_vertices, edges):
    # 거리를 무한대로 초기화합니다.
    dist = [[float('inf')] * num_vertices for _ in range(num_vertices)]
    
    # 자기 자신과의 거리는 0입니다.
    for i in range(num_vertices):
        dist[i][i] = 0
        
    # 주어진 엣지에 대해 초기 거리 설정
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)  # 여러 경로가 있을 경우 최소 거리 설정
    
    # 플로이드-워셜 알고리즘 수행
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

# 입력 받기
num_vertices = int(input("노드의 수를 입력하세요: "))
edges = []

for _ in range(int(input("엣지의 수를 입력하세요: "))):
    u, v, w = map(int, input("엣지를 입력하세요 (u, v, 거리): ").split())
    edges.append((u, v, w))

# 알고리즘 실행
shortest_paths = floyd_warshall(num_vertices, edges)

# 결과 출력
for row in shortest_paths:
    print(row)

코드 설명

이제 코드를 하나씩 살펴보겠습니다.

거리 초기화

우리는 그래프의 노드 수를 기반으로 거리 행렬을 생성합니다. 처음에는 모든 거리를 무한대로 설정한 후, 자기 자신과의 거리는 0으로 설정합니다.

엣지 입력 처리

주어진 엣지 정보를 읽고, 각 노드 간의 초기 거리를 설정합니다. 여러 엣지가 존재하는 경우에는 최소 거리를 선택하도록 합니다.

주요 알고리즘 로직

하게 될 수 있는 세 개의 중첩 루프를 사용하여 모든 쌍의 노드 간의 최단 경로를 계산합니다. 이 루프는 k를 промежуточ한 정점으로 사용하여 i에서 j까지의 최단 경로를 갱신합니다.

실행 예시

알고리즘을 다음과 같이 실행해 보겠습니다:

    노드의 수를 입력하세요: 3
    엣지의 수를 입력하세요: 3
    엣지를 입력하세요 (u, v, 거리): 0 1 3
    엣지를 입력하세요 (u, v, 거리): 0 2 8
    엣지를 입력하세요 (u, v, 거리): 1 2 2

위 예제를 실행했을 때의 출력은 다음과 같습니다:

    [0, 3, 5]
    [inf, 0, 2]
    [inf, inf, 0]

결론

플로이드-워셜 알고리즘은 모든 쌍 최단 경로를 찾는 데에 매우 유용한 알고리즘입니다. 이 알고리즘을 통해 우리는 그래프의 복잡한 구조에서도 효율적으로 최단 경로를 찾아낼 수 있습니다. 다양한 문제를 해결하기 위해 알고리즘을 적용할 수 있는 연습을 해보는 것이 중요합니다. 다음 코딩테스트에서는 이 알고리즘을 사용해 다양한 문제를 풀어보세요!