백준 21278번 - 호식이 두 마리 치킨

호식이 두 마리 치킨 문제 바로 가기

풀이 날짜: 2026-03-21

baekjoon 알고리즘 문제 풀이

풀이 코드


from collections import deque
import sys
input = sys.stdin.readline

INF = int(1e9)
n,m = map(int, input().split())
graph = [[INF]*(n+1) for _ in range(n+1)]

for i in range(1,n+1):
    graph[i][i] = 0

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

for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

min_sum = INF
answer_a = 0
answer_b = 0

for i in range(1,n+1):
    for j in range(i+1,n+1):
        total = 0

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

        total *= 2

        if total < min_sum:
            min_sum = total
            answer_a = i
            answer_b = j

print(answer_a, answer_b, min_sum)

문제 이해

여러 건물과 그 사이를 연결하는 도로가 주어졌을 때, 두 개의 건물을 치킨집으로 선택하여 전체 이동 거리의 합을 최소화하는 문제이다. 각 건물에서 치킨집까지의 거리는 최단 거리 기준으로 계산하며, 왕복 시간이므로 최종 거리 합은 2배로 계산해야 한다. 결국 두 개의 치킨집 위치를 잘 선택하여 모든 건물에서의 이동 비용을 최소화하는 것이 핵심이다.

접근 방법

이 문제는 두 단계로 나누어 접근할 수 있다. 먼저, 모든 건물 간의 최단 거리를 구해야 한다. 이후 두 개의 치킨집을 선택하는 모든 경우를 탐색하면서 각 경우마다 전체 거리 합을 계산하고 최소값을 찾는다. 즉, “최단 거리 계산 + 조합 완전 탐색” 구조로 해결할 수 있다.

핵심 아이디어 (플로이드 워셜)

건물의 개수가 최대 100개이므로, 모든 건물 간 최단 거리를 구하기 위해 플로이드 워셜 알고리즘을 사용하였다. 2차원 배열 graph를 생성하여 각 건물 간 거리를 저장하고, 직접 연결된 경우는 1로, 자기 자신은 0으로 초기화한다. 이후 세 겹의 반복문을 통해 모든 노드 쌍에 대한 최단 거리를 계산하면, graph[a][b]에는 a에서 b까지의 최소 이동 거리가 저장된다.

치킨집 위치 선택

최단 거리 계산이 끝나면, 두 개의 치킨집 위치를 선택해야 한다. 이를 위해 이중 반복문을 사용하여 (i, j) 형태로 모든 건물 조합을 탐색한다. i < j 조건을 두어 중복 선택을 방지하고, 가능한 모든 경우를 완전 탐색한다.

거리 합 계산 방식

각 치킨집 조합이 주어졌을 때, 모든 건물에 대해 가장 가까운 치킨집까지의 거리를 계산해야 한다. 이를 위해 각 건물 k에 대해 graph[k][i]와 graph[k][j] 중 더 작은 값을 선택한다. 이는 해당 건물에서 두 치킨집 중 더 가까운 곳을 이용한다는 의미이며, 이 값을 모든 건물에 대해 누적하여 총 이동 거리를 계산한다.

왕복 거리 처리

문제에서는 이동이 왕복으로 이루어지므로, 계산된 총 거리 값에 2를 곱해 최종 이동 시간을 구한다.

내가 헷갈렸던 포인트

이 문제의 핵심은 단순히 최단 거리를 구하는 것이 아니라, 그 결과를 기반으로 모든 조합을 비교하는 데 있다. 특히 각 건물에서 “더 가까운 치킨집을 선택한다”는 점을 코드로 구현하는 부분이 중요하며, 이를 위해 min(graph[k][i], graph[k][j]) 형태의 계산이 사용된다.

Vienna sausage