[백준] 호석이 두 마리 치킨 21278번 (Python)

문제

컴공 출신은 치킨집을 하게 되어있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두마리 치킨"이다.

이번에 키친 도시로 분점을 확보하게 된 호석이 두마리 치킨은 도시 안에 2개의 매장을 지으려고 한다. 도시는 N 개의 건물과 M 개의 도로로 이루어져 있다. 건물은 1번부터 N번의 번호를 가지고 있다. i 번째 도로는 서로 다른 두 건물 Ai 번과 Bi 번 사이를 1 시간에 양방향으로 이동할 수 있는 도로이다.

키친 도시에서 2개의 건물을 골라서 치킨집을 열려고 한다. 이 때 아무 곳이나 열 순 없어서 모든 건물에서의 접근성의 합을 최소화하려고 한다. 건물 X 의 접근성은 X 에서 가장 가까운 호석이 두마리 치킨집까지 왕복하는 최단 시간이다. 즉, "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 2개를 골라서 치킨집을 열려고 하는 것이다.

컴공을 졸업한 지 30년이 넘어가는 호석이는 이제 코딩으로 이 문제를 해결할 줄 모른다. 알고리즘 퇴물 호석이를 위해서 최적의 위치가 될 수 있는 건물 2개의 번호와 그 때의 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 출력하자. 만약 이러한 건물 조합이 여러 개라면, 건물 번호 중 작은 게 더 작을수록, 작은 번호가 같다면 큰 번호가 더 작을수록 좋은 건물 조합이다.

입력

첫 번째 줄에 건물의 개수 N과 도로의 개수 M 이 주어진다. 이어서 M 개의 줄에 걸쳐서 도로의 정보 Ai , Bi 가 공백으로 나뉘어서 주어진다. 같은 도로가 중복되어 주어지는 경우는 없다. 어떤 두 건물을 잡아도 도로를 따라서 오고 가는 방법이 존재함이 보장된다.

출력

한 줄에 건물 2개가 지어질 건물 번호를 오름차순으로 출력하고, 그때 모든 도시에서의 왕복 시간의 합을 출력한다.

만약 건물 조합이 다양하게 가능하면, 작은 번호가 더 작은 것을, 작은 번호가 같다면 큰 번호가 더 작은 걸 출력한다.

제한

• 2 ≤ N ≤ 100
• N-1 ≤ M ≤ N×(N - 1)/2
• 1 ≤ Ai , Bi​ ≤ N (Ai  ≠ Bi)

예제 입력 1

5 4
1 3
4 2
2 5
3 2

예제 출력 1

1 2 6

위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 작은 건물 번호를 출력해야 함을 유의하자.

---

풀이방법

• 플로이드-와샬 알고리즘에 대해 공부했다.
  • <link> 플로이드 와샬
• 초기 _map은 본인 노드는 0 나머지는 inf을 갖는 2차원 배열이다.
• 점과 점을 잇는 간선을 입력 받으면 2차원 배열에 1을 넣는다.
• 각 노드가 서로에게 갈 수 있는 가중치를 세는 플로이드 와샬 알고리즘을 사용
• 치킨집은 2개이므로 1, 2일때 1,3일때...4,5일때 하나씩 체크한다.
  • 체크한 거리를 더한값과 그때 치킨1, 치킨2의 위치를 튜플에 담는다.
• 가중치, 치킨1, 치킨2순으로 정렬한다.

import sys

input = sys.stdin.readline().rstrip().split()
# 건물의 개수 n, 도로의 개수 m
n, m = map(int, input)

chicken1 = 0
chicken2 = 0

_map = [[float('inf') for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            _map[i][j] = 0
        else:
            _map[i][j] = float('inf')

for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    _map[a-1][b-1] = _map[b-1][a-1] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            _map[i][j] = min(_map[i][j], _map[i][k] + _map[k][j])

count = 0
answer = []
for i in range(n):
    for j in range(n):
        count = 0
        chicken1 = i
        chicken2 = j
        if chicken1 != chicken2:
            for k in range(n):
                if k != chicken1 and k != chicken2:
                    count += min(_map[k][chicken1], _map[k][chicken2])
        else:
            continue
        count *= 2
        answer.append((i,j, count))

answer = sorted(answer, key = lambda x: (x[2], x[0], x[1]))

c1 = answer[0][0]+1
c2 = answer[0][1]+1
s = answer[0][2]

if c1 < c2:
    print(c1, c2, s)
else:
    print(c2, c1, s)