[BOJ/백준] 21278 호석이 두 마리 치킨 파이썬

문제 링크 : https://www.acmicpc.net/problem/21278

21278번: 호석이 두 마리 치킨

 

건물의 개수가 최대 100개고 모든 건물사이의 최단 거리를 구해놓으면 쉬우므로 플로이드 와샬로 해결하였다.

 

입력으로 반은 건물로 배열을 구성하는데 가중치는 1로 넣자

그리고 플로이드 와샬로 각점에 대해서 최단거리를 구해 놓자.

 

다음 치킨집을 지으려는 매장 두곳을 골라야한다.

이중포문으로 골라도 되지만 귀찮으니 combinations을 사용했다.

두개의 위치를 고르고 거리의 총합을 계산한다. 이때 왕복 거리이므로 각 거리의 두개를 해서 더해주자.

그리고 고른 두곳은 거리 계산에 포함되지 않아야하므로 넘어가주자.

 

합을 다 구했다면 최대값을 갱신해주고 이때 갱신된다면 두곳의 좌표도 갱신해주자.

 

from sys import stdin
from itertools import combinations

INF = 9876543210
input = stdin.readline

n,m = map(int, input().split())
dist = [[INF]*n for _ in range(n)]

for _ in range(m):
    a,b = map(int, input().split())
    dist[a-1][b-1]=dist[b-1][a-1]=1

def solv():
    set_board()
    answer_a=answer_b=0
    answer_total = INF
    for a,b in combinations(range(n),2):
        total = 0
        for idx in range(n):
            if idx in (a,b):
                continue
            total += min(dist[a][idx],dist[b][idx])*2
        if total < answer_total:
            answer_total = total
            answer_a,answer_b=a,b
    print(answer_a+1,answer_b+1,answer_total)
def set_board():
    for k in range(n):
        for i in range(n):
            if k == i:
                continue
            for j in range(n):
                if i == j:
                    continue
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

solv()