99클럽 코테 스터디 1일차 TIL + 플로이드-워셜 알고리즘

❇️오늘의 학습 키워드 : 플로이드-워셜 알고리즘

 

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

- 모든 정점 간의 최단 경로를 구하기 위한 알고리즘

- 한 정점에서 모든 다른 정점까지의 최단 거리를 구하는 다익스트라와 달리, 모든 정점 쌍에 대해 최단 경로를 찾는 데 집중!

플로이드-워셜 알고리즘의 동작 원리

- 동적 계획법을 이용해 최단 경로를 점진적으로 구해나간다.

-  경유지 k를 하나씩 추가하면서, i -> j 로 바로 가는 것보다 i -> k -> j 로 가는 경로가 더 짧으면 최단 거리 테이블을 갱신

    (1) i == j 인 경우 0으로 설정 + 간선이 존재하는 i -> j 에 대해 가중치 입력. 경로가 없으면 INF로 초기화

    (2) 정점 k를 경유지로 사용해, k를 경유해서 가는 경로가 더 짧으면 모든 i -> j 쌍을 i -> k -> j로갱신

    (3) 모든 i -> j 에 대해 최단 거리가 테이블에 기록됨

플로이드-워셜 알고리즘의 특징

- 세 개의 for문을 사용하기 때문에 시간복잡도는 O(n^3) -> 정점 수 크면 비효율적!

- 모든 정점 쌍에 대한 최단 거리를 한 번에 구할 수 있음

- 음수 가중치가 포함된 그래프에서도 최단 경로를 구할 수 있음

플로이드-워셜 알고리즘 코드 예제

# 무한대 값을 나타내기 위해 매우 큰 수로 설정
INF = float('inf')

def floyd_warshall(n, graph):
    # dp 테이블 초기화 (최단 거리 테이블)
    dp = [[INF] * n for _ in range(n)]
    
    # 그래프 초기화
    for i in range(n):
        for j in range(n):
            if i == j:      # 자기 자신까지의 거리는 0
                dp[i][j] = 0
            elif graph[i][j] != 0:  # 간선이 존재하면 그 가중치로 초기화
                dp[i][j] = graph[i][j]
    
    # 경유지 k를 통한 최단 거리 갱신
    for k in range(n):      # k는 경유지
        for i in range(n):  # i는 출발지
            for j in range(n):  # j는 도착지
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

    return dp

 

❇️오늘의 회고

  - 항해99 코테스터디 1일차 문제를 통해 놓치고 있었던 플로이드 워셜 알고리즘에 대해서 정확히 학습할 수 있었다.

  - 1일차 문제를 풀 때 처음엔 dp 테이블을 만들었었는데, 최단경로를 구하는 것이 아니므로 굳이 이용할 필요가 없어 삭제하고 주어진 테이블에 덮어쓰기했다.

  - 플로이드-워셜 알고리즘은 구현이 간단하지만 3중 for문으로 시간복잡도가 문제라 정점 수를 꼭 확인해야 한다! 이번 문제에서는 100개밖에 되지 않아 이용할 수 있었다.

  - 내일 11시, 문제를 풀기 전에 위 개념을 한번 더 복습하고 내일 문제에 사용된 알고리즘에 대해서 공부할 것이다!🙂