Chap 17. 최단경로 - Q37. 플로이드

1. 플로이드

• 난이도
  • 중하
• 풀이 시간
  • 40분
• 시간 제한
  • 1초
• 메모리 제한
  • 256MB
• 출처
  • 11404번: 플로이드 (acmicpc.net)

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😊 1차 시도 (성공)

"""
Date    : 2021.11.23
Update  : 2021.11.23
Source  : Q37_플로이드.py
Purpose : 플로이드 알고리즘을 사용하여 모든 도시의 최소 비용을 인접행렬로 구함
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""

# 도시의 개수
n = int(input())
# 버스의 개수
m = int(input())

# 모든 도시의 인접행렬
array = [[1e9] * n for _ in range(n)]

# 대각 행렬 초기화
for i in range(n):
    array[i][i] = 0

# 버스 정보 입력
for i in range(m):
    src_city, dest_city, cost = list(map(int, input().split()))

    array[src_city-1][dest_city-1] = min(cost, array[src_city-1][dest_city-1])

# i -> j 까지 가는데 최소 비용 구함 (플로이드로)
for k in range(n):
    for i in range(n):
        for j in range(n):
            array[i][j] = min(array[i][k] + array[k][j], array[i][j])

# 만약 i -> j로 갈 수 없다면 0으로 출력
for i in range(n):
    for j in range(n):
        if array[i][j] == 1e9:
            array[i][j] = 0

        print(array[i][j], end=' ')
    print()

# print(*array, sep='\n')

c. 🙄 회고

내 풀이

• 출력 예시가 인접행렬 구조라서 플로이드 워셜 알고리즘을 사용했다.

결론

• 앞으로도 코드 상단에 요약 주석을 달고, 다른 곳에도 세세하게 달아보는 연습을 해야겠다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

A에서 B로 가는 버스가 1대 이상일 수 있고, B에서 A로 가는 버스가 1대 이상일 수 있다. 그래서 처음 버스 정보를 입력할 때, 버스 노선 중 최소 비용을 가지는 노선만 입력해야한다.

a. 책 답안

python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] baekjoon. 11404번: 플로이드 (acmicpc.net). Baekjoon. (accessed Nov 5, 2021)