[Python] 백준 #21278 호석이 두마리 치킨

도시 안에 2개의 매장을 지으려고 한다.
도시는 N 개의 건물과 M 개의 도로로 이루어져 있다.
건물은 1번부터 N번의 번호를 가지고 있다.
i 번째 도로는 서로 다른 두 건물 Ai 번과 Bi 번 사이를 1 시간에 양방향으로 이동할 수 있는 도로이다.
키친 도시에서 2개의 건물을 골라서 치킨집을 열려고 한다.
접근성의 합을 최소화하려고 한다.
건물 X 의 접근성은 X 에서 가장 가까운 호석이 두마리 치킨집까지 왕복하는 최단 시간이다.
즉, "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 2개를 골라서 치킨집을 열려고 하는 것이다.
만약 이러한 건물 조합이 여러 개라면, 건물 번호 중 작은 게 더 작을수록, 작은 번호가 같다면 큰 번호가 더 작을수록 좋은 건물 조합이다.

• 플로이드 와샬 알고리즘을 이용해야함

플로이드 와샬 알고리즘

• 거쳐가는 노드를 기준으로 최단 거리를 구하는 방법
  1에서 5로 바로 가는 방법과
  1-> 2, 2-> 5로 가는 방법의 가중치 중에 더 작은 것을 선택하는 방법이다

알고리즘 구현

• inf로 세팅된 배열
• (n,n)을 제외하고 inf로 세팅된 배열 준비

#거쳐가는 노드
for k in range(N):
    #출발노드
    for i in range(N):
        #도착노드
        for j in range(N):
            if(Map[i][k] + Map[k][j] < Map[i][j]):
                #거쳐가는 노드가 더 짧다면
                Map[i][j] = Map[i][k] + Map[k][j]

이 코드를 거치면 정점에서 정점까지 이동하는 비용이 모두 계산된다.

호석이 두마리 치킨

import sys
from itertools import combinations

sys.stdin = open('./input.txt')

N,M = map(int, sys.stdin.readline().split())

Map = [[float("inf") if i != j else 0 for i in range(N)] for j in range(N)]

for i in range(M):
    t, s = map(int, sys.stdin.readline().split())
    Map[t-1][s-1] = 1
    Map[s-1][t-1] = 1

#거쳐가는 노드
for k in range(N):
    #출발노드
    for i in range(N):
        #도착노드
        for j in range(N):
            if(Map[i][k] + Map[k][j] < Map[i][j]):
                #거쳐가는 노드가 더 짧다면
                Map[i][j] = Map[i][k] + Map[k][j]

sum = float('inf')
for comb in combinations([i for i in range(N)],2):
	#치킨집을 세울 두개의 정점을 고름
    temp = 0
    for i in range(N):
        temp += min(Map[comb[0]][i], Map[comb[1]][i])
    if temp < sum:
        sum = temp
        point1 = comb[0]+1
        point2 = comb[1]+1

print(point1, point2, sum*2)