[백준] 21278번: 호석이 두마리 치킨(Python, 플로이드워셜)

문제링크

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

21278번: 호석이 두 마리 치킨

풀이

- combinations로만 풀기엔 시간초과가 나는게 뻔해서 고민했다. 완전 탐색 문제인데 어떻게 다 돌지?

- 질문게시판에 플로이드 워셜로 하면 금방 다그래서 봤더니 진짜 금방이다:)

- 모든 지점 -> 모든 지점은 플로이드워셜, 최단 경로 알고리즘으로만 생각했는데 완전 탐색도 포함이니까 잊지말자!

from itertools import combinations
import sys
input = sys.stdin.readline
INF = 10e9

N, M = map(int, input().split())
graph = [[INF] * (N + 1) for _ in range(N + 1)]

for i in range(N + 1):
    for j in range(N + 1):
        if i == j:
            graph[i][j] = 0

for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

# 플로이드워셜
for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

cities = [i for i in range(1, N + 1)]# 조합으로 2개씩 뽑아놓은것 만들기
chickens = list(combinations(cities, 2))

# 각 도시별로 2개 치킨집에 대한 최소 거리를 저장한다

result = (10e9, 1, 2)
for chicken in chickens:
    a, b = chicken
    temp = 0
    for city in cities:
        temp += min(graph[city][a], graph[city][b])
    if result > (temp, a, b):
        result = (temp, a, b)

print(result[1], result[2], result[0] * 2)