악곱 == 악성곱슬

플로이드

---

이 문제는 임의의 지점에 두 개의 치킨집을 오픈해서 모든 지점에서부터 치킨집까지 거리가 최소가 되게 하는 문제이다.

따라서 모든 지점부터 모든 지점 까지의 최소 거리가 필요하고, 이는 all - all 최단경로인 플로이드를 사용해야겠다는 아이디어를 얻을 수 있다.

1. 모든 지점의 거리를 INF로 초기화 하고, 자기 자신은 0으로 초기화한다.
2. 주어지는 간선 정보에 따라 연결이 되어있으면 1로 초기화한다. 양방향임에 주의하자
3. floyd를 사용해 모든 노드까지의 최단거리를 구한다
4. 2개의 치킨집이므로 완전 탐색을 해도 nC2, 100C2 이므로 미리 구해놓은 table을 사용하면 복잡하지 않다. 따라서 2중 반복문을 사용해 전부 구해본다.

구현

---

import sys

def floyd(n):
    for k in range(1, n+1):
        dist[k][k] = 0
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

def solution(n):
    floyd(n)
    answer = INF
    x, y = 0, 0
    for i in range(1, n):
        for j in range(i+1, n+1):
            rtt = 0
            for c in range(1, n+1):
                rtt += min(dist[i][c], dist[j][c])
            if rtt < answer:
                answer = rtt
                x, y = i, j
    print(x, y, answer*2)

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    INF = int(1e9)
    dist = [[INF] * (N+1) for _ in range(N+1)]
    for _ in range(M):
        A, B = map(int, sys.stdin.readline().rstrip().split())
        dist[A][B] = 1
        dist[B][A] = 1
    solution(N)