백준 치킨 배달 [15686] 파이썬(Python) 코드 + 해설

백준 15686 치킨 배달 문제

문제 설명

도시가 N×N 크기의 2차원 격자로 주어집니다. 각 칸에는 빈 칸(0), 집(1), 치킨집(2) 중 하나가 있다.

도시의 치킨 거리는 모든 집의 치킨 거리의 합입니다. 여기서 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.

프랜차이즈 본사에서는 수익을 극대화하기 위해 일부 치킨집을 폐업시키려고 한다. 최대 M개의 치킨집을 남기고 나머지는 폐업시킬 수 있다. 이때, 도시의 치킨 거리를 최소화하는 방법을 찾는 것이 문제의 목표이다.

입력 및 제한 조건

• 첫째 줄: N(2 ≤ N ≤ 50), M(1 ≤ M ≤ 13)
• 둘째 줄부터 N개의 줄에 도시 정보가 주어진다.
  • 0: 빈 칸
  • 1: 집 (집의 개수는 최소 1개 이상, 최대 2N개 이하)
  • 2: 치킨집 (치킨집의 개수는 M 이상, 13 이하)

목표

• 폐업시키지 않을 M개의 치킨집을 선택하여 도시의 치킨 거리를 최소화하는 것
• 도시의 치킨 거리는 모든 집의 치킨 거리의 합

문제 접근

이 문제는 조합을 사용한 완전 탐색(브루트 포스) 문제이다.

치킨집의 수가 최대 13개이므로, 그중 M개를 선택하는 조합의 수는 최대 (13CM)이다.

이는 최대 약 286개(13C6) 정도로, 문제에서 제한한 시간(1초) 내에 충분히 가능한 처리 속도이다.

단계별 접근 방법

1. 입력 데이터 파싱:
   • 집의 위치와 치킨집의 위치를 각각 리스트로 저장한다.
2. 치킨집 조합 생성:
   • 모든 치킨집 중에서 M개를 선택하는 조합을 생성한다.
3. 도시의 치킨 거리 계산:
   • 각 조합에 대해 다음을 수행:
     • 각 집에 대해 선택된 치킨집들과의 거리를 계산하여 최소값을 찾는다.
     • 모든 집의 치킨 거리의 합을 계산한다.
     • 최소 치킨 거리를 갱신한다.
4. 최소 치킨 거리 출력:
   • 모든 조합을 탐색한 후, 최소 치킨 거리를 출력한다.

코드 구현(Python)

import sys
from itertools import combinations

input = sys.stdin.readline

# 입력 받기
N, M = map(int, input().split())
city_map = [list(map(int, input().split())) for _ in range(N)]

# 집과 치킨집의 위치 저장
houses = []
chickens = []
for i in range(N):
    for j in range(N):
        if city_map[i][j] == 1:
            houses.append((i, j))
        elif city_map[i][j] == 2:
            chickens.append((i, j))

# 치킨집 조합 생성
chicken_combinations = combinations(chickens, M)

# 도시의 치킨 거리 계산
min_city_chicken_distance = float('inf')
for chicken_comb in chicken_combinations:
    city_chicken_distance = 0
    for hx, hy in houses:
        chicken_distance = float('inf')
        for cx, cy in chicken_comb:
            distance = abs(hx - cx) + abs(hy - cy)
            if distance < chicken_distance:
                chicken_distance = distance
        city_chicken_distance += chicken_distance
        # 최적화: 현재 도시 치킨 거리가 최소값보다 크면 더 이상 계산하지 않음
        if city_chicken_distance >= min_city_chicken_distance:
            break
    else:
        if city_chicken_distance < min_city_chicken_distance:
            min_city_chicken_distance = city_chicken_distance

print(min_city_chicken_distance)

코드 설명

• 입력 처리 및 초기화:
  • sys.stdin.readline()을 사용하여 입력 속도를 높인다.
  • 도시의 정보를 2차원 리스트로 저장한다.
• 집과 치킨집의 위치 저장:
  • 이중 반복문을 통해 도시를 순회하며 집과 치킨집의 위치를 저장한다.
• 치킨집 조합 생성:
  • itertools.combinations를 사용하여 치킨집 중에서 M개를 선택하는 모든 조합을 생성한다.
• 도시의 치킨 거리 계산:
  • 각 조합에 대해 모든 집의 치킨 거리를 계산하고 더한다.
  • 최적화를 위해 현재 도시 치킨 거리가 최소값보다 크거나 같으면 더 이상 계산하지 않고 다음 조합으로 넘어간다.
• 결과 출력:
  • 최소 도시 치킨 거리를 출력한다.

결과

15685 백준 치킨 배달 정답

 

도움이 되셨다면 공감과 댓글 부탁드립니다.