[백준] 15686번 치킨 배달 파이썬

NxN 크기의 도시(빈 칸, 치킨집, 집 중 하나)

(r, c) : r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸

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

도시의 치킨 거리 == 모든 집의 치킨 거리의 합

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

0 == 빈 칸, 1 == 집, 2 == 치킨집

 

도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개

 

도시의 치킨 거리가 가장 작게 될 때를 고려.

 

- 입력

1줄 : N(2<=N<=50) , M(1<=M<=13)

2~N줄 : 도시의 정보(0, 1, 2 / 적어도 1개 존재 / 2N개 초과X / 치킨집 개수는 M보다 크거나 같고 13보다 작거나 같음.)

 

- 출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개 골랐을 때, 도시의 치킨 거리의 최솟값

 

15686번 치킨 배달

import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())
city = list(list(map(int, input().split())) for _ in range(n))
result = 999999
house = []  # 집의 좌표
chick = []  # 치킨집의 좌표

#도시 생성
for i in range(n):
    for j in range(n):
        if city[i][j] == 1: #집
            house.append([i, j])
        elif city[i][j] == 2: #치킨집
            chick.append([i, j])

for chi in combinations(chick, m):  # m개의 치킨집 선택
    temp = 0 # 도시의 치킨 거리
    for h in house: 
        chi_len = 999 # 각 집마다 치킨 거리
        for j in range(m):
            chi_len = min(chi_len, abs(h[0] - chi[j][0]) + abs(h[1] - chi[j][1]))
        temp += chi_len
    result = min(result, temp)

print(result)

 

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

15686번: 치킨 배달

참고 : https://codesyun.tistory.com/185

[BOJ / 백준] 15686번 치킨 배달 파이썬(Python) 문제 풀이