[구현] 백준 15686번 '치킨 배달' (Python)

<문제 링크>

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

15686번: 치킨 배달

---

<문제 풀이>

1. 일반 집과 치킨집 좌표 구하기

2. 모든 치킨집 중에서 m개의 치킨집을 뽑는 조합 구하기

3. 조합 하나씩 꺼내서 집마다 가장 가까운 치킨집 거리 구하고 다 더하기

4. 다 더한 치킨집 거리에서 최소 값 구하기

 

<코드>

n,m = map(int,input().split())
city = []
chicken = []
home = []

for i in range(n):
    city.append(list(map(int,input().split())))
    if 2 in city[i]:
        for j in range(n):
            if city[i][j]==2:
                chicken.append((i,j))
    if 1 in city[i]:
        for k in range(n):
            if city[i][k]==1:
                home.append((i,k))
                
from itertools import combinations

def get_sum(candidate):
	result = 0
    for hx, hy in home:
    	tmp = 1e9
        for cx, cy in candidate:
        	tmp = min(tmp, abs(hx-cx) + abs(hy-cy))
        result += tmp
    return result

result = 1e9
for candidate in list(combinations(chicken,m):
    result = min(result, get_sum(candidate))
print(result)

 

<고쳐야 할 점>

• 집마다 가장 가까운 치킨집을 구해야 하고, 그 값을 다 더한 값에서 최솟값을 구해야 함
• 복습 알고리즘