🟩 [백준] [Python] [구현] 15686번_치킨 배달

문제

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

15686번: 치킨 배달

풀이

# 백준 15686번 문제 - 치킨 배달
import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())
graph = 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 graph[i][j] == 1:
            house.append([i, j])
        elif graph[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)

풀다가 답은 맞았는데 틀렸다고 해서 도저히 생각이 안나서 다른 사람의 풀이를 보고 해결하였다.

combination을 사용할 생각은 하지도 못했다. 

 

 

출처

https://codesyun.tistory.com/185