[백준] 15686. 치킨 배달

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

브루트포스를 이용하여 모든 경우의 수를 다 살펴봐야 하는 문제이다.

 

처음에는 greedy, 혹은 bfs로 푸는 방법을 생각했는데 그냥 치킨집 위치와 집 위치를 각각 저장한 뒤, 치킨집 조합을 기준으로 집 위치를 모두 탐색하며 맨해튼 거리를 갱신해주면 되는 문제였다.

 

어렵게 생각하면 정말 어려운 문제다.. 조합은 itertools로도 만들 수 있으나, 재귀 연습을 위해 재귀로 구현하였다.

 

치킨집 조합을 어떻게 넘겨줄까 생각하다가 set을 이용한 합집합으로 넘겨주었다.

import sys
input = sys.stdin.readline


def comb(start, my_set:set):                  # combination 만드는 함수 (재귀 이용)
    global ans
    if len(my_set) == m:
        dist = [n*n+1] * h_len                # 치킨집 조합마다 거리 정보 새롭게 저장
        for t_y, t_x in my_set:
            for idx in range(h_len):          # 치킨집위치 마다 맨해튼 거리 업데이트 (최소가 되게)
                dist[idx] = min(dist[idx], abs(t_y - house[idx][0]) + abs(t_x - house[idx][1]))
        ans = min(ans, sum(dist))             # 맨해튼 거리가 작으면 ans 업데이트
        return

    for num in range(start, c_len):
        comb(num+1, my_set | {chicken[num]})  # 합집합으로 combination 넘겨줌


n, m = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(n)]
chicken = []
house = []
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:                  # 집 위치 모두 저장
            house.append((i, j))
        if city[i][j] == 2:                  # 치킨집 위치 모두 저장
            chicken.append((i, j))

c_len = len(chicken)
h_len = len(house)
ans = float('inf')
comb(0, set())
print(ans)