파이썬 알고리즘 280번 | [백준 11404 번] 플로이드 - DP

280 플로이드 - DP

1) 어떤 전략(알고리즘)으로 해결?

• DP

2) 코딩 설명

• 플로이드 워셜 기반 문제 풀이

<내 풀이>

import sys

n = int(sys.stdin.readline()) 
m = int(sys.stdin.readline())
bus = [[ int(1e9) for _ in range(n+1) ] for _ in range(n+1)]

for i in range(1,n+1):
        bus[i][i] = 0

for i in range(m) : 
    s,e,c = map(int,sys.stdin.readline().split())
    bus[s][e] = min(bus[s][e], c)

# n개의 줄을 출력해야 한다. 
# i번째 줄에 출력하는 j번째 숫자는 
# 도시 i에서 j로 가는데 필요한 최소 비용이다. 
# 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력

for k in range(1,n+1) :
    for i in range(1,n+1) :
        for j in range(1,n+1) : 
            bus[i][j] = min(bus[i][j], bus[i][k]+bus[k][j])

for i in range(1,n+1) :
    for j in range(1,n+1) :
        if bus[i][j]<1e9 :
            print(bus[i][j], end=" " )
        else : 
            print(0, end = " ")
    print()

<내 틀렸던 풀이, 문제점>

(1) 틀린 이유 하나

• 초기화 시, 버스 한 번 탑승 시 비용이 10만을 넘어가지 않는다고 해서 2차원 배열 초기화 시 100001 로 해주었다.
• 무한으로 초기화하지 않아도 괜찮을 것이라고 생각했었는데 비용이 십만보다 작다는 것은 버스 한번 탈 때의 비용이 십만을 넘지 않는다는 것이었다.
• 그래서 최단 비용은 십만을 넘을 수도 있는 것!

(2) 틀린 이유 둘

• 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 라는 조건 때문!!
• 이 노선들 중에서 최소인 애를 bus 에 저장해주어야 함

import sys

n = int(sys.stdin.readline()) 
m = int(sys.stdin.readline())
bus = [[ 1000001 for _ in range(n+1) ] for _ in range(n+1)]

for i in range(1,n+1):
        bus[i][i] = 0

for i in range(m) : 
    s,e,c = map(int,sys.stdin.readline().split())
    bus[s][e] = c

# n개의 줄을 출력해야 한다. 
# i번째 줄에 출력하는 j번째 숫자는 
# 도시 i에서 j로 가는데 필요한 최소 비용이다. 
# 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력

for k in range(1,n+1) :
    for i in range(1,n+1) :
        for j in range(1,n+1) : 
            bus[i][j] = min(bus[i][j], bus[i][k]+bus[k][j])

for i in range(1,n+1) :
    for j in range(1,n+1) :
        if bus[i][j]<=100000 :
            print(bus[i][j], end=" " )
        else : 
            print(0, end = " ")
    print()

<반성 점>

• 문제를 잘 읽자

<배운 점>

• 플로이드 워셜 개념 : dp 이고 점화식 & 3중 for문 => O(N^3)
• DP는 처음에 무한대로 초기화 & 들어오는 노드 정보 따라 최소 비용 등록

for k in range(1,n+1) :
	for i in range(1,n+1) : 
    	for j in range(1,n+1) :
        	dp[i][j] = min( dp[i][j] , dp[i][k] + dp[k][j] )
        

• 파이썬에서 무한 표시 : int(1e9)

• 개념 REFERENCE : https://freedeveloper.tistory.com/385