[백준/Python] 플로이드

https://www.acmicpc.net/problem/11404

11404번: 플로이드

이 문제는 전형적인 최단 경로 문제이며 플로이드 워셜 알고리즘을 이용하면 수월하게 풀 수 있었다. 플로이드 워셜 알고리즘을 알아야 풀 수 있어서 이 알고리즘을 모른다면 아래의 링크를 참고하면 좋을 것 같다.

 

https://it-garden.tistory.com/247

플로이드-워셜(Floyd-Warshall) 알고리즘 이론과 파이썬 구현

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 c < graph[a][b]: # 가장 짧은 정보만 저장
    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: # 도달할 수 없는 경우엔 0 출력
      print(0, end = " ")
    else:
      print(graph[a][b], end = " ")
  print()

모든 지점에서 모든 지점까지 최소 비용을 구해야하는 문제이므로 플로이드 워셜 알고리즘을 사용해야 한다. graph는 모든 지점에서 모든 지점까지 최소 비용을 담는 2차원 리스트이다. 리스트를 n 까지가 아닌 n+1 까지로 생성한 이유는 도시의 번호와 리스트의 인덱스를 맞추기 위해서이다. ( 도시의 번호가 1부터 시작하므로!) 

 

1. 반복문을 통해 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화한다.

2. 반복문을 통해 입력받은 버스의 정보로 비용을 초기화한다. 이 때 중요한 것은 문제에서 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다" 라고 했으므로 if c < graph[a][b] 조건이 꼭 필요하다. 가장 짧은 정보만 저장할 수 있도록 한다.

3. 플로이드 워셜 알고리즘을 수행한다. 

4. 수행 결과를 출력한다. 이 때 문제에서 도달할 수 없는 경우에는 0을 출력하라고 했으므로 조건문을 통해 출력을 다르게 해주어야 한다.