[BOJ-15686] 치킨배달

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

15686번: 치킨 배달

---

[풀이]

Brute Force를 이용했다.

물론 조합을 DFS로 구현할 수 있다. 해도 무방하다.

DFS공부겸 조합을 나타내는 것도 나쁘지 않은 것같다. (귀찮...ㅋㅋ)

라이브러리도 많이 알면 좋다. (나보다 더 잘하는 사람들이 고심해서 만든거니까?)

 

(1) 집의 좌표(MAP[y][x]=1)와 치킨집의 좌표(MAP[y][x]=2)를 찾는다.

집좌표는 houses에 넣고, 치킨집의 좌표는 chickens에 넣는다 ~

 

(2) 각 집좌표의 치킨거리를 구한다.

"치킨거리": 집과 가장 가까운 치킨집 사이거리

 

집의 좌표: (hy, hx), 치킨집 좌표: (cy, cx) 일 때

집과 치킨집의 사이거리는 abs(hy, cy)+abs(hx, cx) 이다. 

 

나는 딕셔너리를 이용하여 각 집에서 각 치킨집과의 사이거리를 저장했다.

chickenStreet[(hy,hx,cy,cx)]=abs(hy, cy)+abs(hx, cx)

 

 

(3) 조합을 이용하여 M개의 치킨집을 구하는 경우의 수를 구한다.

최대 M개의 치킨집만 고를 때 이런 경우 때문에 고민했다.

예를 들자면 1번집은 3번 치킨집이 제일 가깝고,

2번집은 3번과 4번 치킨집이 제일 가깝고

3번집은 5번 치킨집이 제일 가까울 때와 같은 치킨집의 개수가 M보다 큰 경우에

 

3번 치킨집, 4번치킨집을 그냥 둔다면=> 3번집한테서 가장 가까운 치킨집 5번은 폐점하게된다.

그러면 조합을 이용하여 M개의 치킨집을 구하는 경우의 수를 구한다.

 

(4) 각 조합에서 구한 M개의 치킨집들 중에서 도시의 치킨 거리를 구한다.

"도시의 치킨 거리": 모든 집의 치킨 거리의 합

"치킨거리": 집과 가장 가까운 치킨집의 사이거리

 

집좌표와 M개의 치킨집들의 사이거리를 구하여, 가장 짧은 거리(치킨 거리)를 구한다.

집좌표의 개수만큼 치킨거리들을 구하여 합치면 도시의 치킨거리를 구하게된다.

이부분이 치킨집들을 M개 조합원소 중 하나이다.

 

result는 도시의 치킨거리의 최솟값이다.

---

[코드 Python]

import sys
from itertools import combinations
input=sys.stdin.readline
#N:2~50, M:1~13
N,M= map(int, input().strip().split())
MAP=[ [*map(int, input().strip().split())] for _ in range(N)]

#1. 집좌표와 치킨집 좌표를 구한다.
chickens=[]
houses=[]
for y in range(N):
    for x in range(N):
        if MAP[y][x]==1:
            houses.append((y,x))
            
        elif MAP[y][x]==2:
            chickens.append((y,x))

#집좌표의 각원소들의 치킨거리를 구한다.
chicken_street={}
for house in houses:
    hy, hx= house
    for chicken in chickens:
        cy, cx=chicken
        chicken_street[(hy,hx,cy,cx)]=abs(hy-cy)+abs(hx-cx)

#combinations 라이브러리를 이용하여 치킨집M개를 뽑는다.
cases=[*combinations(chickens,M)]
result=float('inf')
for case in cases:
    street=0
    for house in houses:
        hy, hx= house
        tmp=float('inf')
        #집좌표(hy, hx)의 치킨거리를 찾는다.
        for c in case:
            cy,cx=c
            tmp=min(tmp, chicken_street[(hy,hx,cy,cx)])
        street+=tmp
    result=min(result, street)

print(result)