치킨 배달 (백준 15686번)

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

15686번: 치킨 배달

 

 

이 문제는 주어진 치킨집에서 도시의 치킨거리가 최소가 되는 치킨집 m개를 뽑는게 관건인 문제이다.

 

집에서 치킨집까지의 거리중 최소 거리를 치킨거리 라고한다. 따라서 집마다 치킨거리는 한 개씩 나올 것이며, 이 모든 치킨거리를 합한것이 도시의 치킨거리이다.

참고로 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구할 수 있다.

---

도시의 치킨거리가 최소가 되도록 치킨집을 뽑는것이 도저히 생각나지 않아서 조합을 사용해봤다.

 

만약 치킨집의 갯수가 k개라면 그중 m개를 뽑는 경우의 수는 kCm이 되는데, 기본적으로 주어지는 치킨집의 갯수 범위는 m <= 치킨집 <= 13이다. 따라서 최대 경우의 수는 13개에서 m개를 선택하는 경우, 즉 최대 100,000을 넘기지 않을 것이다.

그래서 치킨집들중 m개를 뽑는 경우의 수를 계산하는데 1초를 넘기지 않을 것이라고 생각했다.

 

참고로 조합을 뽑는 함수는 itertools의 combination을 사용했다.

combination은 리스트와 리스트에서 몇개를 고를지를 나타내는 정수를 인자로 받는다. 뽑는 경우를 튜플에 넣어 준다. 그리고 반환형이 list가 아니므로 캐스팅을 해줘야 쓸 수 있다.

list(combination(list, n))

 

치킨집 중 m개를 뽑아서, 각 집의 치킨거리를 구하도록 했다. 그렇게 구한 치킨 거리로 도시의 치킨 거리를 구하고 sum_list에 넣어서 모든 경우의 수를 돈 후,  min 메서드로 도시의 치킨거리가 최소가 되는 값을 반환하도록 했다.

 

코드는 다음과 같다.

import sys
from itertools import combinations
n, m = map(int, sys.stdin.readline().split())

matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

chick_list = []
home_list = []
# 치킨집과 집을 찾아서 리스트에 넣어준다.
for i in range(n):
    for j in range(n):
        if matrix[i][j] == 1:
            home_list.append((i, j))
        elif matrix[i][j] == 2:
            chick_list.append((i, j))
            
# 각 집의 치킨거리가 저장되는 리스트
h_to_c = []

# 치킨집들 중 m개를 뽑아서 튜플로 저장해준다.
chick_comb = list(combinations(chick_list, m))

# m개를 뽑은 각 경우의 도시 치킨거리를 저장하는 리스트
sum_list = []

for chick_list in chick_comb:
    h_to_c.clear()
    for home in home_list:
        min_d = 99
        hx, hy = home

        for chick in chick_list:
            cx, cy = chick
            distance = abs(cx - hx) + abs(cy-hy)
            if min_d > distance:
                min_d = distance
        h_to_c.append(min_d)
    sum_list.append(sum(h_to_c))
print(min(sum_list))