알고리즘 스터디 14일차

목차

1. 플로이드-워셜

2. [플로이드-워셜 실전 문제]

 

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

1. 플로이드-워셜

그래프에서 최단 거리를 구하는 알고리즘 (대표적으로 다익스트라, 벨만포드, 플로이드워셜)

모든 노드 간에 최단 경로 탐색

음수 가중치 에지가 있어도 수행 가능

동적 계획법의 원리를 이용해 알고리즘에 접근

시간 복잡도 : O(V³)  (시간복잡도가 효율적이지 않으므로 주어진 데이터가 적으면 플로이드-워셜을 고려해보자.)

 

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

위 식은 S->E를 갈때 중간의 K(출발과 도착을 제외한 모든 노드)가 최적일때 (min = 최단거리) 를 찾는다는 뜻

 

리스트를 선언하고 초기화하기

최단 거리 리스트에 그래프 데이터 저장하기, D[S][E] = W 형태로 인접행렬로 표현

3중 for문의 형태로 반복하면서 리스트의 값을 업데이트

3중 for문 식 외우기! (K는 제일 바깥쪽)

 

 

 

1. 플로이드-워 실전 문제

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

11404번: 플로이드

 

해설 코드

import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
distance = [[sys.maxsize for j in range(N+1)] for i in range(N+1)] #sys.maxsize : 무한대

# 거리의 대각선을 0으로 초기화(자기자신으로 가는 거리)
for i in range(1, N+1):
    distance[i][i] = 0

# s:시작, e:도착, v:가중치
for i in range(M):
    s, e, v = map(int,input().split())
    if distance[s][e] > v: # 입력된 값보다 들어온 가중치가 작다면 작은 값으로 업데이트(최단거리 찾기 위함)
        distance[s][e] = v

# 플로이드-워셜 (해당 코드는 외우기)
# i에서 j까지 가는 최단거리에서 k를 거쳐가는 거리가 작다면 최단거리 업데이트
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1, N+1):
            if distance[i][j] > distance[i][k] + distance[k][j]:
                distance[i][j] = distance[i][k] + distance[k][j]

# 결과 출력, 최단거리가 sys.maxsize면 0출력(경로 없다는 의미)
for i in range(1,N+1):
    for j in range(1,N+1):
        if distance[i][j] == sys.maxsize:
            print(0,end=' ')
        else:
            print(distance[i][j], end=' ')
    print()

 

시간 복잡도가 비효율적인점만 빼면 코드도 비교적 간단하고 음수가중치가 있어도 사용가능하다는 점이 매력적이였다.

플로이드-워셜의 3중 for문만 외워둔다면 그래프 문제에서 많이 사용할 수 있을 것 같다. (N이 적다면)