[백준 / Python] 15696번: 치킨 배달

문제 링크:

문제 이해

---

• N×N 행렬으로 표시되는 도시가 있다. 각 칸은 0(빈칸), 1(집), 2(치킨집) 중 하나이다.
• “치킨 거리” 란 집과 가장 가까운 치킨집 사이의 거리이다.
• 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 $∣$r1-r2$∣$ + $∣$c1-c2$∣$로 구한다.

• 도시에 있는 치킨집 중에서 M개를 고를 때, 도시의 치킨 거리가 가장 작은 경우 구하기
  
  
  

• 최종적으로 구해야 하는 것: 치킨 거리의 최솟값
• 중간 과정으로 구해야 하는 것:
  1. 전체 치킨 가게 중 남아있을 M개의 치킨 가게의 조합
  2. 각각의 조합에서 도시의 치킨 거리 계산
     
     
     
     
     
     

해결 전략

---

1. 도시 행렬에서 DFS로 집, 치킨집 좌표 찾기(dict 형태로 저장)
2. DFS로 전체 K개의 치킨 가게 중 M개 치킨가게 조합 탐색
3. 각 조합에서, 도시의 한 집에서 조합 내에 존재하는 모든 치킨집과의 거리를 계산. 이 중 가장 짧은 거리가 해당 집의 치킨거리. 이렇게 모든 집에 대한 치킨거리 계산하고 더해줌(도시의 치킨거리) ⇒ 치킨거리 min값 return!
   
   
   
   
   
   

구현 코드, 풀이

---

import sys
from collections import defaultdict

def solution(coord, N, M):
 
    def dfs(elements, start, m):
        if m == 0:
            combination.append(elements[:])
            return

        for i in range(start, N + 1):
            elements.append(i)
            dfs(elements, i+1, m-1)
            elements.pop()
  
    combination = []
    dfs([], 1, M)

    comb_distance = []
    for idx, c in enumerate(combination):
        chicken_distance = 0

        for house in coord['house']:
            house_chicken_dist = []

            for j in range(len(c)):
                id = c[j] - 1
                chicken = coord['chicken'][id]
                house_chicken_dist.append(abs(house[0] - chicken[0]) + abs(house[1] - chicken[1]))

            chicken_distance += min(house_chicken_dist)
        comb_distance.append(chicken_distance)
    return min(comb_distance)

# input
N, M = map(int, input().split())
city = []
for _ in range(N):
    index = list(map(int, input().split()))
    city.append(index)

if __name__ == '__main__':
      
    coord = defaultdict(list)
    for i in range(N):
        for j in range(N):
            if city[i][j] == 2:
                coord['chicken'].append([i, j])
            elif city[i][j] == 1:
                coord['house'].append([i, j])

    print(solution(coord, len(coord['chicken']), M))

1. main 블록:
   • 입력: N(도시의 크기), M(남길 치킨집의 최대 개수), N x N 크기의 도시 정보 city **list 에 저장
   • 이중 반복문을 통해 각 위치에 따라 치킨집과 집의 위치를 coord **dict에 저장한다.
   • solution 함수를 호출하여 최소 거리를 출력
2. solution 함수:
   • 함수는 coord dict와 함께 동작한다. coord dict는 ‘house’와 ‘chicken’ 두 가지 키를 갖고 있다. ‘house’ 키에는 집의 위치 리스트가, ‘chicken’ 키에는 치킨집의 위치 리스트가 담겨 있다.
   • dfs 함수에서 조합(combination)을 구하기 위해 깊이 우선 탐색(DFS)을 수행. 조합의 길이가 M이 되면 해당 조합을 combination 리스트에 추가.
   • 모든 조합에 대해 각 집에서 가장 가까운 치킨집까지의 거리를 계산
     • 모든 치킨집과의 거리 계산해서 house_chicken_dist 에 저장
     • 이 중 min값이 해당 집의 치킨거리가 됨. 치킨거리를 comb_distance 리스트에 저장.
   • 최종적으로 comb_distance 리스트에서 최솟값을 반환함.