[코드트리 챌린지] 2주차 - 병원 거리 최소화하기 🥇5

병원 거리 최소화하기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

⭕ CODE

from itertools import combinations
n, m = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(n)]

ho = []
pe = []

for i in range(n):
    for j in range(n):
        if arr[i][j] == 2:
            ho.append([i,j])
        elif arr[i][j] == 1:
            pe.append((i,j))

hospital = list(combinations(ho,m))
r = []

for i in hospital:
    d = 0
    for a in pe:
        result = []
        for j in i:
            x = j[0]
            y = j[1]
            result.append(abs(a[0]-x) + abs(a[1]-y))
        d += sorted(result)[0]
    r.append(d)

print(sorted(r)[0])