[baekjoon] 백준 15686번(파이썬): 치킨 배달

문제

15686번: 치킨 배달

알고리즘

- 반복문을 통해 집의 좌표와 치킨집의 좌표를 구한다.

- 구한 치킨집을 combinations를 통해 m개를 선택 후 각 집마다 치킨집의 거리를 구한다.

- 그때의 모든 경우의 수중 집과 치킨집의 거리의 최솟값을 구한 후 출력한다.

코드

import sys
from itertools import combinations

n, m = map(int, sys.stdin.readline().split())
graph = list(list(map(int, sys.stdin.readline().split())) for _ in range(n))
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])

answer = sys.maxsize
for chi in combinations(chick, m): # combinations을 통해 m개의 치킨집 선택
    temp = 0 # 도시의 치킨 거리
    for h in house:
        chi_len = sys.maxsize # 각 집마다 치킨 거리
        for k in range(m):
            chi_len = min(chi_len, abs(h[0] - chi[k][0]) + abs(h[1] - chi[k][1]))
        temp += chi_len
    answer = min(answer, temp)

print(answer)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법