[알고리즘][Python] 백준 15686 치킨 배달 문제 풀이

문제 출처 :www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

문제 해석 : 치킨 거리는 가장 가까운 치킨 집까지의 거리를 의미합니다. 이 문제에서는 도시 전체의 치킨 거리를 최소가 되게 하면서 치킨 집을 일정 숫자만큼 폐업 시켜야합니다.

 

문제 풀이 :  구현 문제 입니다. 가능한 모든 경우를 고려하여 치킨 집을 정해진 갯수만큼 배치하고 거리를 계산하여 최솟값을 찾아야합니다.

---

풀이 코드

from itertools import combinations

N, M = map(int, input().split())

arr = []

for _ in range(N):
    arr.append(list(map(int, input().split())))

def check():
    sum_a = 0

    for i in range(N):
        for j in range(N):

            if arr[i][j] == 1:
                min_dist = 2e9

                for x in range(N):
                    for y in range(N):
                        if arr[x][y] == 2:
                            dist = abs(i -x) + abs(j-y)
                            min_dist = min(dist, min_dist)

                sum_a += min_dist
    return sum_a

candidate = []

for i in range(N):
    for j in range(N):
        if arr[i][j] == 2:
            candidate.append([i,j])
            arr[i][j] = 0

test = list(combinations(candidate, M))
answer = 2e9

for element in test:
    for x,y in element:
        arr[x][y] = 2
    answer = min(answer, check())
    for x,y in element:
        arr[x][y] = 0

print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.