11404

날짜 : 2023. 03. 22

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())  # 도시 개수
m = int(sys.stdin.readline())  # 버스의 개수
graph = [[int(1e9)] * (n+1) for _ in range(n+1)]  # 그래프 초기화

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())  # 시작, 도착, 비용
    graph[a][b] = min(graph[a][b], c)  # a -> b 일 때 c의 비용 (같은 노선, 다른 비용 존재 가능)
    
for k in range(1, n+1):  # 경유
    for i in range(1, n+1):  # 출발
        for j in range(1, n+1):  # 도착
            if i == j:  # 자기자신 -> 0
                graph[i][j] = 0
            else:
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

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

 

 

풀이

- 플로이드 워셜 알고리즘을 활용해 풀이한다.

 

 

알게된 점

- 예제에서 계속 틀리길래 확인해봤더니 입력부분에서 같은 경로상의 다른 비용인 버스가 있어서 이를 비교 후 최신화하는 과정을 생략했었다.

- 이후에 97%에서 틀리길래 유사 질문들을 확인해본 결과 도달할 수 없는 케이스(int(1e9) 출력)에 대하여 조건문을 붙이지 않았기 때문에 이를 수정 후 정답처리를 받을 수 있었다.

 

 

참고 사이트

- https://freedeveloper.tistory.com/385

[이것이 코딩 테스트다 with Python] 31강 플로이드 워셜 알고리즘