백준 11404

<가장 빠른 버스노선 구하기>

난이도 : 골드 4

1. 백준 문제
   11404

2. 코드 알고리즘

• 플로이드 워셜

최단거리 구하는 알고리즘으로 음수 가중치가 있어도 수행 가능하며(벨만포드와 동일) 동적 계획법 원리를 사용한다

아래의 점화식을 이용한 알고리즘이다

D[출발노드][도착노드] = Math.min(D[출발노드][도칙노드], D[출발노드][경유노드]+D[경유노드][도착노드])

• 11404 풀이

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수도 있음을 주의한다.

2-1. 슈도 코드

11404

N 도시 개수
M 노선 개수
D = N*N 행렬 선언하기, sys.max로 초기화

# D 초기화
for i 도시 개수:
	D[i][i] = 0 으로

# D에 가중치 저장
for i in 노선 개수:
	D[a][b] = w #가로줄이 출발노드, 세로 줄이 도착노드

#플로이드-워셜 알고리즘 수행
for 가중치 in 도시개수:
	for 시작노드 in 도시개수:
		for 도착노드 in 도시개수:
			if D[i][j] > D[i][k] + D[k][j] #원래 최단 거리 > i에서 k 최단거리 + k에서 j 최단거리
				#즉 k를 경유해 가는게 더 짧다는 얘기이므로
				D[i][j] = D[i][k] + D[k][j] 

for i in 노드:
	for j in 노드:
		if sys.max이면: 가는 경로 없음 -> 0 출력
		else:
			D[i][j] 출력
 

3. 코드

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

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())

max = sys.maxsize
D = [[max for j in range(N+1)] for i in range(N+1)] #6*6 행렬
#D 초기화
for i in range(1, N+1):
    D[i][i] = 0

#D에 가중치 저장
for i in range(M):
    a,b,c = map(int, input().split()) #a가 출발노드, b가 도착노드, c가 가중치
    if D[a][b] > c: #max인경우에도, 이미 입력된 경로 있을 경우에도
        D[a][b] = c #노선이 이미 있는 경우에도 가중치가 더 작은 노선으로 바꾸기

#플로이드-워셜 알고리즘 수행
for K in range(1,N+1): #k가 가장 먼저 온다는 게 중요_즉, 가중치 우선으로 전개
    for S in range(1, N+1):
        for E in range(1, N+1):
            if D[S][E] > D[S][K] + D[K][E]: #D[x][y]에서 x가 출발노드, y가 도착노드
                D[S][E] = D[S][K] + D[K][E] #K를 경유해서 가는 게 더 짧을 경우 업데이트

for i in range(1, N+1):
    for j in range(1, N+1):
        if D[i][j] == max:
            print(0, end=" ")
        else:
            print(D[i][j], end=" ")
    print("")

4. 코드 후기

• 이미 앞서 최단 경로를 구하는 방법은 충분히 배웠다고 생각했다. 그런데 부분의 경로를 가져와 더해서 최단 거리를 구할 수 있다는 방법은 생각하지 못했었다.
  최단 경로를 구하는 방법이 이렇게나 다양한게 신기... 가장 알고리즘이 간단하고 명료한 건 플로이드 알고리즘인 것 같다.
  시간복잡도가 큰게 단점!

• 두 도시를 연결하는 노선이 여러개인줄은 몰랐다. 여기서 시간 소비... 여러개의 노선이 있을 경우 우리가 관심있는 건 최단 경로 일뿐이므로 최소 가중치의 노선만 찾자!

• 플로이드 워셜 알고리즘에서 가장 중요한건 3중 for문 에서 K 중심으로 전개한다는 것이다.
  K를 기준으로 K와 연결되있는 앞뒤의 Start 노드랑 End 노드를 찾아 최단 경로를 찾는 것이었다.
  K가 기준임을 기억하기!