[백준] 11404 플로이드

백준 11404번 플로이드

그래프 이론 / 플로이드 워셜

 

 

[문제]

 

 

모든 도시의 최단거리 출력문제이므로 한점에서 이동하는 다익스트라보다는 플로이드 워셜이 더 알맞다.

 

 

입출력 예시)

'1 4 1'과 '1 4 2'가 서로 경로가 겹치는 것이 보인다.

해당 경우에 거리비용이 더 작은 것으로 갱신하는 작업이 별도로 필요하다.

 

 

 

[과정]

 

플로이드 알고리즘은 약간 dfs/bfs + dp 문제인 것 같다.

점화식을 사용해서 2중 반복문을 사용하면 다익스트라보다 쉽게 구현할 수 있다.

 

• 거리 2차원 배열(graph)을 최대값(1e9)로 초기화
• 2중 반복문으로 자기자신의 경로는 0으로 초기화
• 간선정보를 저장
• 해당 그래프 좌표의 거리비용과 모든 경우의 수의 거리비용 중 최솟값으로 해당 좌표의 거리비용(graph[a][b])을 갱신
• graph 출력

 

 

 

[소스코드]

 

# 플로이드  2022-06-28

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 i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0

# 간선정보 입력
for i in range(m):
    a,b,c = map(int, input().split())
    graph[a][b] = min(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()

import sys가 없다면 시간초과가 뜬다.

 

---

 

 

[통과]

아래 둘다 코드는 동일한데 처음은 print()문을 안지워서, 두번째는 import sys를 안적어서 오류!