PS Featured

[PS] BOJ 15686 / 치킨 배달

Minjun Kim

10 Dec 2025 • 4 min read

Thumbnail: Photo by Maksym Tymchyk 🇺🇦 (Unsplash)

문제 링크: https://www.acmicpc.net/problem/15686

치킨이 먹고 싶습니다.

풀이

단계 별로 생각하기

$N \times N$ 크기의 도시에 현재 $L$개의 치킨집이 있습니다. 이 중 $M$개만 남기고 나머지를 모두 없앨 때, 도시의 치킨 거리의 최솟값을 구하는 문제입니다.

풀이를 단계 별로 나눠서 생각해봅시다.

치킨집을 $M$개만 남기기
1의 상태에서 도시의 치킨 거리 계산하기
1과 2를 반복하며 도시의 치킨 거리의 최솟값 찾기

1) 치킨집을 $M$개만 남기기

현재 있는 $L$개의 치킨집 중 $M$개만 남기려고 합니다.
백트래킹을 통해, $L-M$개의 치킨집을 전체 치킨집에서 골라 지우도록 구현했습니다.

# 1. M개의 치킨집만 남기고 다 빈칸으로 치우기
min_dist = INF # 도시의 치킨 거리의 최솟값

def dfs(depth, next_idx):
    """백트래킹으로 치킨집을 M개만 남기고 지우기"""
    if depth == CHICKEN_REMOVE: 
        # 3. 도시의 치킨 거리의 최솟값 구하기.
        ...
        return
    
    for i in range(next_idx, len(CHICKEN_COORDS)):
        r, c, remains = CHICKEN_COORDS[i]
        if not remains: # 이미 지워진 치킨집인지 확인한다. 
            continue

        # (r, c)의 치킨집을 지우고 백트래킹
        CITY[r][c] = 0
        CHICKEN_COORDS[i][2] = False
        dfs(depth + 1, i + 1)
        # 다시 기존 값 복구하기
        CITY[r][c] = 2
        CHICKEN_COORDS[i][2] = True

dfs(0, 0)
print(min_dist)

치킨집을 지우는 백트래킹 코드

2) 도시의 치킨 거리 계산하기

1에서 남긴 $M$개의 치킨집으로 도시의 치킨 거리를 계산합니다.

치킨 거리란, 어떤 하나의 집에서 임의의 치킨집 $K$로의 맨해튼 거리(택시 거리로도 알려져 있습니다.)의 최솟값이며, 도시의 치킨 거리는 모든 집의 치킨 거리의 합입니다.

따라서, 모든 집에 대해서 모든 치킨집으로의 거리를 계산한 뒤 그 최솟값들의 합을 계산하면 됩니다.

# 2. 현재 도시의 상태를 기반으로 도시의 치킨 거리 계산하기
def calc_city_distance():
    """현재 도시의 치킨 거리 계산하기"""
    dist = 0
    for home_r, home_c in HOUSE_COORDS:
        cur_dist = INF
        for chicken_r, chicken_c, flag in CHICKEN_COORDS:
            if flag: # 현재 남아있는 치킨집에 대해서만 거리 계산
                cur_dist = min(cur_dist, distance(home_r, home_c, chicken_r, chicken_c))
        dist += cur_dist
                
    return dist

도시의 치킨 거리를 계산하는 함수

3) 도시의 치킨 거리의 최솟값 구하기

2에서 정의한 함수를 백트래킹의 종료 지점에서 호출해, 그 결과의 최솟값을 전역 변수로 기록합니다.

min_dist = INF # 도시의 치킨 거리의 최솟값

def dfs(depth, next_idx):
    """백트래킹으로 치킨집을 M개만 남기고 지우기"""
    if depth == CHICKEN_REMOVE: 
        # 3. 도시의 치킨 거리의 최솟값 구하기.
        global min_dist
        min_dist = min(min_dist, calc_city_distance())
        return
    
    ... # 이전과 동일

도시의 치킨 거리의 최솟값 구하기

전체 코드

input = open(0).readline
INF = 100_001

def distance(r1, c1, r2, c2):
    """두 2차원 좌표의 맨해튼 거리(택시 거리)를 계산한다."""
    return abs(r1 - r2) + abs(c1 - c2)

N, M = map(int, input().split())
CITY = [[0] * N for _ in range(N)]

HOUSE_COORDS = []
CHICKEN_COORDS = []
for r in range(N):
    for c, v in enumerate(map(int, input().split())):
        CITY[r][c] = v
        if v == 1:
            HOUSE_COORDS.append((r, c))
        elif v == 2:
            CHICKEN_COORDS.append([r, c, True])

CHICKEN_REMOVE = len(CHICKEN_COORDS) - M

# 풀이 과정
# 1. M개의 치킨집을 제외한 나머지 칸을 빈칸으로 처리
# 2. 해당 상태의 도시의 치킨 거리 구하기
# 3. 도시의 치킨 거리의 최솟값 구하기

# 2. 현재 도시의 상태를 기반으로 도시의 치킨 거리 계산하기
def calc_city_distance():
    """현재 도시의 치킨 거리 계산하기"""
    dist = 0
    for home_r, home_c in HOUSE_COORDS:
        cur_dist = INF
        for chicken_r, chicken_c, flag in CHICKEN_COORDS:
            if flag: # 현재 남아있는 치킨집에 대해서만 거리 계산
                cur_dist = min(cur_dist, distance(home_r, home_c, chicken_r, chicken_c))
        dist += cur_dist
                
    return dist

# 1. M개의 치킨집만 남기고 다 빈칸으로 치우기
min_dist = INF # 도시의 치킨 거리의 최솟값

def dfs(depth, next_idx):
    """백트래킹으로 치킨집을 M개만 남기고 지우기"""
    if depth == CHICKEN_REMOVE: 
        # 3. 도시의 치킨 거리의 최솟값 구하기.
        global min_dist
        min_dist = min(min_dist, calc_city_distance())
        return
    
    for i in range(next_idx, len(CHICKEN_COORDS)): # 이전에 탐색한 지점의 이후부터 탐색해야 중복되는 경우를 제외할 수 있다.
        r = CHICKEN_COORDS[i][0]
        c = CHICKEN_COORDS[i][1]
        if CITY[r][c] != 2:
            continue
        CITY[r][c] = 0
        CHICKEN_COORDS[i][2] = False
        dfs(depth + 1, i + 1)
        CITY[r][c] = 2
        CHICKEN_COORDS[i][2] = True

dfs(0, 0)
print(min_dist)

solution.py