[Python] 백준 15686 치킨 배달

2025 상반기 현대 오토에버 신입 채용 코테 2번이랑 비슷?

문제 분석

• 각 칸은 빈 칸 (0) / 집 (1) / 치킨 집 (2)
• r, c는 1부터 시작
• 치킨 거리 : 집과 가장 가까운 치킨 집 사이의 거리 → 치킨 거리는 집을 기준으로 결정
• 각 집은 치킨 거리를 가지고 있다.
• 도시의 치킨 거리 = 모든 집의 치킨 거리의 합
  
  
• (r1, c1) ~ (r2, c2) 사이의 거리 = |r1 - r2| + |c1 - c2|
• 가장 많은 수익을 낼 수 있는 치킨집의 개수는 최대 M개라고 했을 때,
• 최대 M개를 고르고, 나머지 치킨집은 모두 폐업 시킨다.
• 최대 m개의 치킨집을 남겼을 때, 도시의 치킨 거리의 쵯소값을 구하라

 

코드 설계

1. 도시 입력
2. 전체 치킨 집 수 구하기
   1. 전체 치킨집의 좌표를 chickens 리스트에 저장
3. 전체에서 m개 선택 → 순서 x, 중복 x : 조합 (combinations)
   1. 선택되지 않은 치킨집의 좌표를 0으로 대체
4. m개의 치킨집에 대한 도시의 치킨 거리 구하기
   1. 도시의 치킨거리 구하기
      1. 돌면서 집을 발견하면 가장 가까운 치킨의 집을 찾기
         1. bfs? dfs? 다 거리를 확인할 필요는 없을거 같은데..
         2. 거리를 구하는 공식이 있으니 집을 찾고 각 치킨집에 대한 거리 중 최소값 구하기
      2. 해당 치킨집과의 거리 구하기
5. 이 중 최솟값 출력

 

정답 코드

import sys
input = sys.stdin.readline
from itertools import combinations

def find_dis(house, chicks) :
    min_distance = float('inf')
    x, y = house
    # print('chicks : ', chicks)
    for i in range(len(chicks)) :
        cx, cy = chicks[i]
        min_distance = min(min_distance, (abs(x-cx) + abs(y-cy)))
    return min_distance

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

# 1. 치킨집들의 좌표 저장
before_chick = []
for r in range(n) :
    for c in range(n) :
        if city[r][c] == 2 :
            before_chick.append([r,c])

# 2. 전체에서 m개 선택 → 순서 x, 중복 x : 조합 (combinations)
after_chick = []
for i in combinations(before_chick, m) :
    after_chick.append(i) # 남겨질 m개씩 치킨집 조합

# 3. 모든 m개의 치킨집 조합에 대해 도시 치킨 거리 구하기 -> 최소 거리 찾기
for i in range(len(after_chick)) :
    # print('현재 m개의 치킨집 좌표 : ', after_chick[i])
    new_city = city # 폐업 후 도시

    # 원래 있던 치킨집이 새로운 조합 m개 안에 속하지 않는다면 폐업 (2->0)
    for b in before_chick :
        if b not in after_chick[i] :
            x, y = b
            new_city[x][y] = 0
    # print(new_city)

    # 4. 현재 남아있는 치킨집에 대한 도시 치킨 거리 구하기
    distance = []
    for r in range(n) :
        for c in range(n) :
            if new_city[r][c] == 1 : # 4-1. 집 찾기
                # 4-2. 집과 치킨집들 사이의 거리 구하기 : 그 중 짧은 치킨집이 해당 집의 치킨 거리
                distance.append(find_dis((r,c), after_chick[i]))

    city_chick_distance.append(sum(distance))

print(min(city_chick_distance))