Python/구현 BOJ-15686 치킨배달

Posted on | In

[Python/구현] BOJ-15686 치킨배달

📌문제링크 풀이참고


*풀이참고 링크 들어가셔서 보시면 됩니다.


도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다.
도시의 치킨 거리의 최소값을 구하는 문제다.

✔ 치킨집 중 M개를 선택한 조합별 도시의 치킨거리를 계산하여 최소값을 도출하면된다.


1. combinations 함수 사용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
from itertools import combinations
input = sys.stdin.readline

N,M = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)] # 0은 빈 칸, 1은 집, 2는 치킨집

chicken_store = []; homes=[]
for x in range(N):
    for y in range(N):
        if board[x][y] == 2 :
            chicken_store.append([x,y])
        elif board[x][y] == 1 :
            homes.append([x,y])
combs = list(combinations(chicken_store,M))
result = sys.maxsize 

for comb in combs : # 조합 수 만큼 for문
    sumv =0
    for home in homes : # 집별 치킨거리 구하기
        sumv += min([abs(home[0] - i[0]) + abs(home[1] - i[1]) for i in comb])
        if result <= sumv : break # 도시의 치킨거리보다 커질 경우 볼 필요 없음
    result = min(sumv, result)
print(result)