[BOJ] 백준 11404 플로이드 (python 파이썬)

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

11404번: 플로이드

 

문제 풀이에 앞서 백준 11404 플로이드 문제는 플로이드-워셜 알고리즘을 이용한 문제이므로 

플로이드-워셜 알고리즘을 이해하고 있으면 좋습니다!

 

플로이드-워셜 알고리즘 관련해서 제가 최근에 정리해둔 글도 있으니 참고해주시면 이해가 더 쉬우실 거에요!

https://zerozero909.tistory.com/41

[Algorithm] 플로이드-워셜 (Floyd-Warshall) 알고리즘

 

백준 11404 플로이드 (파이썬)

 

Step 1 문제 분석하기

 

• 모든 도시의 쌍(A,B)
• n개의 도시 n이 100(작은 편) 
• 필요한 비용의 최솟값 -> 최단거리

-> 플로이드-워셜 알고리즘을 사용하기에 알맞음.

(모든 노드간 최단거리를 찾을 때)

 

• 입력: 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다.
• -> start node, end note, v(가중치) 

 

모든 도시에 쌍과 관련된 최솟값을 찾아야 하는 문제이다.

그래프에서 시작점을 지정하지 않고, 모든 노드와 관련된 최소 경로를 구하는 알고리즘이 바로 플로이드-워셜 알고리즘이다.

도시의 최대 개수(N)이 100개로 매우 작은 편이므로 O(N^3) 시간 복잡도의 플로이드-워셜 알고리즘으로 해결할 수 있다.

 

1. 버스 비용 정보를 인접 행렬에 저장한다. 

먼저 인접 행렬을 초기화한다. 연결 도시가 같으면(i==j) 0, 아니면 충분히 큰 수로 값을 초기화한다.

그리고 주어진 버스 비용 데이터값을 인접 행려레 저장한다.

 

2. 플로이드- 워셜 알고리즘을 수행한다. 다음 점화식을 활용한 3중 for문으로 모든 중간 경로를 탐색한다.

 

플로이드-워셜 점화식
# 두 도시의 연결 비용 중 최솟값
Math.min(distance[S][E], distance[S][K] + distance[K][E])

 

3. 알고리즘으로 변경된 인접 행렬을 출력한다.

인접 행렬 자체가 모든 쌍의 최단 경로를 나타내는 정답 리스트이다. 정답 리스트를 그대로 출력하되, 문제의 요구사항에 따라 두 도시가 도달하지 못할 때 (∞)는 0, 아닐 때는 리스트의 값을 출력한다.

 

 

Step 2 수도코드 작성

N(도시 개수)
M(노선 개수)
distance(노선 데이터를 저장하는 인접 행렬) # 충분히 큰 값으로 초기화

for i를 1 ~ N만큼 반복:
	인접 행렬에 시작 도시와 종료 도시가 같은 자리에 0 저장

for M만큼 반복:
	노선 데이터를 distance 행렬에 저장
    
for k -> N만큼 반복:
	for i -> N만큼 반복:
    	      for j -> N만큼 반복:
        	      distance[i][j]보다 distance[i][k]+ distance[k][j]가 작으면 업데이트
            
            
정답 리스트 출력 ->
리스트의 값이 최초 초기화하기에 충분한 큰 수일 경우 0 출력 # 도착할 수 없는 경로
아니면 리스트의 값 출력

 

 

Step 3 코드 작성

# 백준 11404 플로이드 파이썬

import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
distance = [[sys.maxsize for j in range(N+1)] for i in range(N+1)]

for i in range(1,N+1):
  distance[i][i] = 0

for i in range(M):
  s,e,v = map(int,input().split())
  if(distance[s][e]) > v :
    distance[s][e] = v


# 플로이드 워셜 알고리즘 수행
for k in range(1,N+1):
  for i in range(1,N+1):
    for j in range(1,N+1):
      if distance[i][j] > distance[i][k] + distance[k][j] :
        distance[i][j] = distance[i][k] + distance[k][j]


# 정답 리스트 출력

for i in range(1,N+1):
  for j in range(1,N+1):
    if distance[i][j] == sys.maxsize:
      print(0, end = ' ')
    else:
      print(distance[i][j], end= ' ')
      
  print()

 

 

• 참고자료 인프런 강의 

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148470 

학습 페이지

 

---

플로이드-워셜 알고리즘은 점화식과 3중 for문 구조만 외우고 있는게 핵심인 것 같다.