[Python/파이썬] - 백준(BOJ) 21278번 : 호석이 두 마리 치킨

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

21278번: 호석이 두 마리 치킨

 

각 노드에서 다른 노드까지의 거리를 플로이드 와샬(Floyd-Warshall)을 이용하여 구하고

노드를 두가지 고르는 경우의수를 모두 탐색하여 최소값을 구하는 문제이다.

 

노드와 노드가 연결되어있다면 edge 배열에 양방향으로 거리를 1로 초기화 해주고

플로이드 와샬 알고리즘으로 노드까지의 거리를 전부 구한다.

그리고 두 노드를 고른 뒤 두 노드 제외한 노드와의 거리의 최소값을 저장한다 (min(edge[i][k],edge[j][k]))

이후 [1,2] ~ [n-1,n] 까지 모두 확인하며 최소값을 answer에 저장하고 두 노드를 기록해 준다.

 

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
edge = [[sys.maxsize for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b = map(int,input().split())
    edge[a-1][b-1] = 1
    edge[b-1][a-1] = 1
for k in range(n):
    edge[k][k] = 0
    for i in range(n):
        for j in range(n):
            edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j])

answer = sys.maxsize
first, second = -1, -1
for i in range(n-1):
    for j in range(i+1, n):
        check = 0
        for k in range(n):
            check += min(edge[i][k], edge[j][k]) * 2
            if check >= answer:
                break
        if answer > check:
            answer = check
            first = i+1
            second = j+1

print(first, second, answer)