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

 

문제

 

문제 링크 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

 

 

 

 

CODE

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)

 

 

 

 

 

풀이

💡 idea

- m개의 치킨집을 선택하는 모든 조합에 대해 도시의 치킨 거리를 구한다

- 치킨 거리 : abs(r1-r2) + abs(c1-c2)

 

💡 implementation

- 집과 치킨집의 좌료를 각각 리스트에 저장

- itertools의 combinations를 이용하여 치킨집 리스트 chick에서 m개 선택하고, 치킨 거리 구하기!

 

 

 

 

 

결과