💻 백준 15686번: 치킨 배달

문제 소개 🧐

N×N 크기의 도시에서 빈 칸, 집, 치킨집이 주어졌다. 각 집의 치킨 거리는 가장 가까운 치킨집까지의 거리이며, 도시의 치킨 거리는 모든 집의 치킨 거리의 합이었다. 도시 내 치킨집 중 최대 M개만 남기고 나머지는 폐업시켜, 도시의 치킨 거리가 최소가 되는 경우를 찾는 문제였다.

입력 📝

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다. 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력 📤

폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

제한 ❌

  • 시간: 1초
  • 메모리: 512 MB

나의 풀이: 조합과 완전 탐색 활용 🎉

Idea

도시의 치킨집 개수가 최대 13개로 많지 않았고, 남길 치킨집의 개수 M도 최대 13개였다. 이 점을 고려하여 모든 가능한 치킨집 조합을 탐색하는 완전 탐색(Brute Force) 방식을 떠올렸다. itertools.combinations를 사용하여 전체 치킨집 중에서 M개의 치킨집을 고르는 모든 경우의 수를 만들었다. 각 조합마다 모든 집의 치킨 거리를 계산하고, 그 합인 도시 치킨 거리를 구했다. 이들 중 최소값을 찾는 방식으로 문제를 해결했다.

Code

import sys
import itertools
import heapq

n, m = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
home_idx_list = []
chicken_idx_list = []

for i in range(n):
    for j in range(n):
        if board[i][j] == 1:
            home_idx_list.append((i,j))
        if board[i][j] == 2:
            chicken_idx_list.append((i,j))

# 1. 치킨 인덱스 리스트에서 m 만큼 고른, 인덱스 리스트를 만든다
chosen_idx_list = list(itertools.combinations(chicken_idx_list, m))

# 2. 각 인덱스에서의 도시 치킨 거리를 구한다
chicken_distance_list = []
for idx_li in chosen_idx_list:  # 각 후보 최적 치킨집 리스트
    chicken_distance = 0
    for home in home_idx_list:  # 각 집마다 치킨 거리 구하고
        h_x, h_y = home
        min_dis = float("inf")
        for i in range(m):
            val = 0
            val += abs(idx_li[i][0] - h_x)
            val += abs(idx_li[i][1] - h_y)
            if min_dis > val:
                min_dis = val
        chicken_distance += min_dis
    heapq.heappush(chicken_distance_list, chicken_distance) # 합한 값을 힙푸시

print(heapq.heappop(chicken_distance_list))

Result

성공! ✅

itertools.combinations를 활용하여 모든 경우의 수를 효율적으로 생성하고, 각 경우에 대해 도시 치킨 거리를 계산하여 최솟값을 찾는 방식으로 문제를 해결했다.

배운 점 및 느낀 점 ✍️

  • 조합(Combination)의 활용: itertools.combinations를 사용하면 특정 개수를 선택하는 모든 경우의 수를 쉽게 생성할 수 있다는 것을 다시 한번 확인했다. 완전 탐색 문제에서 매우 유용하게 쓸 수 있는 도구임을 느꼈다.
  • 완전 탐색(Brute Force)의 가능성: 문제의 제약 조건(N, M의 크기)이 충분히 작을 경우, 모든 경우의 수를 탐색하는 완전 탐색이 효과적인 해결책이 될 수 있다. 무작정 복잡한 알고리즘을 생각하기보다 제약 조건을 먼저 확인하는 습관이 중요하다고 느꼈다.
  • 최소 거리 계산: 두 지점 사이의 거리를 *맨해튼 거리( r1-r2 + c1-c2 )* 로 계산하는 방식은 BFS 없이도 간단하게 구현할 수 있었다.
  • 문제 분석의 중요성: 치킨집의 개수가 적다는 점이 이 문제의 핵심 힌트였다. 이처럼 문제의 숨겨진 제약 조건을 파악하는 것이 효율적인 알고리즘을 선택하는 데 큰 도움이 된다는 것을 다시 한번 깨달았다.