[Python] BOJ 21278 - 호석이 두 마리 치킨

www.acmicpc.net/problem/21278

21278번: 호석이 두 마리 치킨

N이 100이하이므로 O(N^3)인 플로이드-와샬 알고리즘을 사용해도 통과가 될 것 같아서 풀어보았다.

 

1. M개 만큼 a와 b를 입력받고 a와 b사이의 거리를 1로 cost배열에 넣어준다.

2. 플로이드-와샬 알고리즘을 통해 각 건물 사이의 거리를 구해준다.

3. 브루트포스 방식으로 치킨집이 1번,2번일 때 부터 1번,3번 ... N-1번,N번까지일 때 모든 도시에서의 왕복 시간의 합을

   비교하며 최솟값을 찾아서 출력한다.

 

import sys
from math import inf
input = sys.stdin.readline
N, M = map(int,input().split())
cost = [[inf] * N for _ in range(N)]
for _ in range(M):
	a,b = map(int,input().split())
	cost[a-1][b-1] = 1
	cost[b-1][a-1] = 1
for k in range(N):
	cost[k][k] = 0
	for i in range(N):
		for j in range(N):
			cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

max = 1000000000
for i in range(N-1):
	for j in range(1, N):
		sum = 0
		for k in range(N):
			sum += min(cost[k][i], cost[k][j])
		if max > sum * 2:
			max = 2 * sum
			dab = [i+1, j+1, 2*sum]
print(*dab)

(solved.ac 티어: 골드 5)

 

# 다른 사람들 풀이를 보니 bfs나 다익스트라로 푸는 방법도 많던데, 한번 시도해봐야겠다.