99클럽 코테 스터디 1일차 TIL 플로이드 워셜

오늘의 학습 키워드: 플로이드 워셜

플로이드 워셜과 다익스트라 알고리즘은 최단경로 알고리즘의 대표적인 예이다. 두 알고리즘은 각각 다른 특징을 가지고 있다.

• 플로이드 워셜
  • 시간 복잡도 : O(V3)
    •  플로이드 워셜은 모든 노드 쌍에 대해 최단 경로를 구하기 때문에 노드수 V에 대해 V * V * V 의 연산이 필요
  • 모든 지점에서 다른 모든 지점까지의 최단경로를 구하는 알고리즘
  • 거쳐가는 모든 노드를 탐색하기 때문에 매 단계 마다 방문하지 않는 노드의 최단 거리를 찾을 필요가 없다.
  • 2차원 테이블에 최단 경로 갱신(모든 지점에서 다른 모든 지점의 경로를 저장해야 함)
  • 점화식에 따라서 2차원 테이블을 갱신 하므로 DP 알고리즘
  • 모든 노드 쌍을 대상으로 하므로, 노드 수가 많아질수록 성능이 감소, 그래프의 노드수가 작을 때 유리
• 다익스트라
  • 시간 복잡도: 인접 리스트에서 우선 순위 큐(힙)을 활용하면  O((V+E)logV) V는 노드 수, E는 간선의 수
  • 한 지점에서 다른 특정 지점 까지의 최단경로를 구하는 알고리즘
  • 단계 마다 방문하지 않는 노드 중에서 최단거리를 갖는 노드(우선 순위 큐등 사용)를 반복적으로 선택하며 최단 경로 갱신
  • 1차원 리스트에 최단 경로 갱신(한 지점에서 특정 지점까지의 최단 경로만 저장)
  • 위 에서 애기한 우선 순위 큐를 사용해서 가중치가 낮은 방문 노드부터 선택하므로 그리디 알고리즘
  • 특정 출발점에 대한 경로 탐색에 유리, 특히 간선이 적은 희소 그래프에 효율적

오늘의 문제: BOJ 11403(경로 찾기)

이 문제의 경우 위에서 설명한 플로이드 워셜로 접근해서 비교적 간단하게 해결할 수 있었다. 문제에서 최단 경로를 요하는 문제는 아니였지만 모든 지점에서 다른 모든 지점들을 방문 할 수 있는지 물어보는 문제로 플로이드 워셜 기본 유형이라고 생각했다. 

n = int(input())

# 0 1 0
# 0 0 1
# 1 0 0
matrix = [list(map(int, input().split()))  for _ in range(n)]

# 플로이드 워셜
for k in range(n):
    for j in range(n):
        for i in range(n):
            if matrix[j][i] == 0:
                # 점화식 규칙
                if matrix[j][k] == 1 and matrix[k][i] == 1:
                    matrix[j][i] = 1

 

처음 그래프의 (j,i)로 방문여부를 표시한  2차원 그래프가 주어지고,  n * n * n으로 탐색하면서 점화식에 규칙에 맞는 조건을 찾으면 방문 여부를 2차원 그래프에 갱신해준다. 이번 문제의 경우 가중치가 없는 방향 그래프였지만 만약 가중치가 주어진다면 

# 플로이드 워셜
for k in range(n):
    for j in range(n):
        for i in range(n):
            if matrix[j][i] == 0:
                # 점화식 규칙
                matrix[j][i] = min(matrix[j][i], matrix[j][k] + matrix[k][i])

 

위의 점화식으로 변경해준다.