백준 15686번 - 치킨 배달
치킨 배달 문제 바로 가기
풀이 날짜: 2026-01-06
baekjoon 알고리즘 문제 풀이
풀이 코드
import sys
input = sys.stdin.readline
from itertools import combinations
n,m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
house = []
chicken = []
for x in range(n):
for y in range(n):
if graph[x][y] == 1:
house.append((x, y))
elif graph[x][y] == 2:
chicken.append((x,y))
answer = float('inf')
dist = [[0]*len(chicken) for _ in range(len(house))]
for i, (hx,hy) in enumerate(house):
for j, (cx,cy) in enumerate(chicken):
dist[i][j] = abs(hx-cx) + abs(hy-cy)
for comb in combinations(range(len(chicken)), m):
city = 0
for i in range(len(house)):
city += min(dist[i][j] for j in comb)
answer = min(answer,city)
print(answer)
문제 핵심 요약:
모든 집에서 ‘가장 가까운 치킨집’까지의 거리(집과 치킨집 사이의 거리)를 구해서 전부 합한 값을 최소로 만드는 것이 목표이다.
- 치킨집 M개 고르기
- 각 집마다 그 M개 중 가장 가까운 치킨집까지 거리 구하기
- 그 거리들을 다 더하기
- 이 합이 최소가 되는 조합 찾기
내 풀이 흐름
내 코드는 크게 4단계로 구성된다.
1) 입력에서 집/치킨집 좌표를 따로 저장하기
- house = [(x,y), …]
- chicken = [(x,y), …] 2) 집-치킨집 거리표 dist 만들기
- dist[i][j] = i번째 집과 j번째 치킨집 사이 3) 치킨집 중 M개를 고르는 모든 조합을 돈다.
- comb = (치킨번호1, 치킨번호2,…) 4) 각 조합마다 도시 치킨 거리를 계산하고 최소값을 갱신한다.
- 각 집 i에 대해 comb 안의 치킨집 거리 중 최소값을 찾아서 더한다.
구현에서 어려웠던 부분
for comb in combinations(range(len(chicken)), m):
치킨집이 예를 들면 5개라면 번호는 0,1,2,3,4가 될 것이다.
여기서 M개를 고르는 모든 경우를 만들기 위해서 combinations(range(5),M)을 사용하는 것이다.
만약 M=2라면 comb는 이렇게 나온다.
- (0,1), (0,2), (0,3), (0,4), (1,2), … 즉, comb는 ‘남길 치킨집들의 번호 묶음’을 의미한다.
city = 0
for i in range(len(house)):
city += min(dist[i][j] for j in comb)
i번째 집을 하나 고르고, 그 집에서 “이번 조합 comb에 포함된 치킨집들” 중에 가장 가까운 치킨집 거리 하나를 고른다.
그 최솟값을 city에 더하고, 모든 집에 대해 반복하면 city가 완성된다.
즉, city는 “이번 치킨집 조합에서의 도시 치킨 거리(모든 집의 최소거리 합)”을 의미한다.