플로이드

❓문제
https://www.acmicpc.net/problem/11404

❗문제 정리
사용한 파라미터 :
n(int) : 도시의 개수
m(int) : 버스의 개수
a: 시작도시
b: 도착도시
c: 푤요한 비용

📑코드

import sys
input=sys.stdin.readline

INF=int(1e9)
n=int(input())
m=int(input())

graph=[[INF]*(n+1)for _ in range(n+1)]

#자기 자신으로 가는 비용 0 으로 초기화
for a in range(1, n+1):
  for b in range(1,n+1):
    if a==b:
        graph[a][b]=0
        
#각 간선에 대한 정보 입력받고, 그 값으로 초기화
for _ in range(m):
    a,b,c=map(int,input().split())
    if graph[a][b]!=INF:
        graph[a][b]=min(c,graph[a][b])
    else:
        graph[a][b]=c
        
for k in range(1, n+1):
  for a in range(1, n+1):
    for b in range(1, n+1):
        graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b])
for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b]==INF:
            print(0,end=' ')
        else:
            print(graph[a][b],end=' ')
    print()

📝코드 설명

INF=int(1e9)
n=int(input())
m=int(input())

graph=[[INF]*(n+1)for _ in range(n+1)]

최단거리 테이블을 무한대로 초기화시키기 위해 INF 변수에 1e9를 대입
도시개수 n, 버스개수 m 입력받기
inf로 채워진 2차원 테이블 받기

(n+1, n+1)크기의 리스트가 필요하다.

#자기 자신으로 가는 비용 0 으로 초기화
for a in range(1, n+1):
  for b in range(1,n+1):
    if a==b:
        graph[a][b]=0

자기 자신->자기 자신으로 가는 비용은 0이므로, graph에 0넣기

#각 간선에 대한 정보 입력받고, 그 값으로 초기화
for _ in range(m):
    a,b,c=map(int,input().split())
    if graph[a][b]!=INF:
        graph[a][b]=min(c,graph[a][b])
    else:
        graph[a][b]=c

간선 정보 입력받기
중복되는 노선은 비용이 더 적은것을 graph에 담도록해야함.
if문을 사용하여 노선이 중복될 경우, 기존 graph값과 새로 입력받은 비용값 중 작은것을 취하도록함.

for k in range(1, n+1):
  for a in range(1, n+1):
    for b in range(1, n+1):
        graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b])

점화식 사용 $D_{ab}=min(D_{ab},D_{ak}+D_{kb})$
k : 거쳐가는 도시
a: 시작 도시
b: 도착도시

for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b]==INF:
            print(0,end=' ')
        else:
            print(graph[a][b],end=' ')
    print()

최단거리 테이블 값 출력하기 인덱스 0은 필요없으므로 1부터 for문 시작
inf인 경우는 0으로 출력하고, 아닌 경우는 가진 수 출력.

🎖제출 결과

💡insight
이코테 플로이드 워셜 알고리즘