✅ BOJ 15686 - 조합 백트래킹

백준 15686 치킨 배달 - 조합 완전탐색

문제 핵심

• N×N 격자에 집(1), 치킨집(2) 있음
• 치킨 거리: 각 집에서 가장 가까운 치킨집까지의 맨해튼 거리
• 도시 치킨 거리: 모든 집의 치킨 거리 합
• 치킨집 중 M개만 남기고 나머지 폐업
• 목표: 도시 치킨 거리 최소화

개념 정리

잘못된 접근법

"거리 멀어서 치킨집 먼저 제거하면 됨" → 아님. 멀어도 특정 집에게는 가장 가까운 치킨집일 수 있음

"치킨집 기준으로 가까운 집 찾기" → 아님. 집 기준으로 가장 가까운 치킨집 찾는 문제임

올바른 접근

조합 + 완전탐색

• 치킨집 최대 13개 → 13CM 경우의 수 매우 적음
• 모든 M개 조합 다 해보면 됨

구현

1. 맨해튼 거리

distance = abs(x1 - x2) + abs(y1 - y2)

BFS/DFS 같은 거 쓸 필요 없음. 그냥 좌표 차이 계산하면 끝.

2. 조합 생성

실전용 - itertools

from itertools import combinations
possible_combinations = combinations(chickens, m)

개념 이해용 - 백트래킹

def make_combinations(chickens, m_count):
    result = []
    selected = []

    def dfs(depth, start_idx):
        if depth == m_count:
            result.append(selected[:])
            return

        for i in range(start_idx, len(chickens)):
            selected.append(chickens[i])
            dfs(depth + 1, i + 1)
            selected.pop()  # 백트래킹

    dfs(0, 0)
    return result

3. 거리 계산

def cal_route(houses, selected_chickens):
    total = 0
    for hx, hy in houses:
        min_dist = float('inf')
        for cx, cy in selected_chickens:
            dist = abs(hx - cx) + abs(hy - cy)
            min_dist = min(min_dist, dist)
        total += min_dist
    return total

전체 코드

import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

houses = []
chickens = []

for r in range(n):
    for c in range(n):
        if board[r][c] == 1:
            houses.append((r, c))
        elif board[r][c] == 2:
            chickens.append((r, c))

def cal_route(houses, selected_chickens):
    total = 0
    for hx, hy in houses:
        min_dist = float('inf')
        for cx, cy in selected_chickens:
            dist = abs(hx - cx) + abs(hy - cy)
            min_dist = min(min_dist, dist)
        total += min_dist
    return total

min_distance = float('inf')

for combo in combinations(chickens, m):
    distance = cal_route(houses, combo)
    min_distance = min(min_distance, distance)

print(min_distance)

핵심 요약

1. 좌표 저장: 집, 치킨집 위치 기록
2. 조합 생성: M개 치킨집 선택하는 모든 경우
3. 거리 계산: 각 집에서 가장 가까운 치킨집까지 거리
4. 최솟값: 모든 조합 중 최소 도시 치킨 거리

치킨집 최대 13개라서 완전탐색 가능. 복잡하게 생각하지 말고 그냥 다 해보면 됨.