Part7.12_동적프로그래밍(DynamicProgramming)_플로이드 워샬 알고리즘
문제
입력
첫 번째 줄에는 도시의 수N(N<=100)과 도로수 M(M<=200)가 주어지고, M줄에 걸쳐 도로정보
와 비용(20 이하의 자연수)이 주어진다. 만약 1번 도시와 2번도시가 연결되고 그 비용이 13이
면 “1 2 13”으로 주어진다.
출력
모든 도시에서 모든 도시로 이동하는데 드는 최소 비용을 아래와 같이 출력한다.
자기자신으로 가는 비용은 0입니다. i번 정점에서 j번 정점으로 갈 수 없을 때는 비용을 “M"으
로 출력합니다.
정답 풀이
- 플로이드 워샬 알고리즘
- 이차원 배열의 모든 값을 5000으로 초기화 한다,
- 가장 먼저 경유 없이 직행으로 갈 수 있도록 갱신한다.
2.3중 for문 구현
가장 상위(3중for문) for문의 k값이 바뀔 때 마다 이중 for문을 돌면서 배열을 갱신한다.
i -> k -> j 일 때(k를 경유할 때) 가장 최솟값으로
정답 코드
import sys
sys.stdin = open ("input.txt", "rt")
def input():
return sys.stdin.readline().rstrip()
if __name__ == "__main__":
#n 은 정점번호, m은 간선의 개수
n, m = map(int,input().split())
# 냅색 알고리즘과 동일한 원리이다.
#경유지를 1부터 N까지 경유해서 가는 방법을 갱신한다
dis=[[5000]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
dis[i][i] = 0 #대각선 0으로 초기화
for i in range(m):#최초로 인접행렬로 초기화(아무 노드 거치지 않고 직행)
a,b,c = map(int,input().split())
dis[a][b] = c
for k in range(1, n+1):# 프로이드 워샬 알고리즘
# k기 바뀔때마다 아래 이차원리스트 갱신.
for i in range(1,n+1):
for j in range(1,n+1):
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
# 다이나믹 테이블 값 갱신 i -> k -> j 를 거쳐서 간 최소값
for i in range(1,n+1):
for j in range(1,n+1):
if dis[i][j] == 5000:
print("M", end=' ')
else:
print(dis[i][j], end=" ")
코멘트
플로이드 워샬 알고리즘 딱딱 나올 수 있도록 공부 더 해놓자
Author And Source
이 문제에 관하여(Part7.12_동적프로그래밍(DynamicProgramming)_플로이드 워샬 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@angel_eugnen/Part7.12동적프로그래밍DynamicProgramming플로이드-워샬-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)