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

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

21278번: 호석이 두 마리 치킨

---

• 문제 : 

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

 

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

 

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

 

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

 

 

 

---

• 풀이 :

플로이드 와샬 알고리즘을 이용한 문제였습니다. 기초적인 문제입니다.

 

여기서 추가적인 아이디어는 치킨집을 차릴 건물 2개를 선택하는 경우를 조합으로 짜서 모든 경우를 탐색하는 것입니다.

 

각 걍우의 두 점에서 다른 모든 점들로 가는 가중치가 최소인 것들의 합에서 두 배를 (왕복이기 때문에) 해주어 그 값이 최소라면 그 때의 두 점을 출력합니다.

 

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
cost = [[float("inf") for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    cost[a-1][b-1] = 1
    cost[b-1][a-1] = 1
for i in range(N): # 자기 자신으로 가는 가중치는 0
    cost[i][i] = 0

for k in range(N): #걍유지
    for i in range(N): #출발지
        for j in range(N): #도착지
            cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

m = [0,0,float("inf")]
for x,y in list([x,y] for x in range(N) for y in range(N)): # 0,1 부터 n-1,n-1까지 모든 조합을 탐색
    tmp = [0 for _ in range(N)] #거리 합을 위해 사용
    for i in range(N):
        if i != x or i != y:
            tmp[i] = min(cost[x][i], cost[y][i])
    s = sum(tmp)*2 # 왕복이므로 거리는 편도의 두 배를 해줘야 함.
    if s < m[2]:
        m = [x+1, y+1, s]
print(' '.join(map(str,m)))