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

- Author: @mildsalmon
- Published: 2021-11-24
- Updated: 2021-11-24
- Source: http://blex.me/@mildsalmon/chap-17-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-q37-%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C
- Tags: 파이썬, 알고리즘, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 백준, 최단

---

# 1. 플로이드

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

### A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.
	
### B. 💡 내 답안

##### a. 😊 1차 시도 (성공)

```python

"""
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)](https://github.com/ndb796/python-for-coding-test/blob/master/17/1.py)

# 참고문헌

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

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