[Python] 백준 15686 치킨 배

🧑‍💻 [Python] 백준 15686 치킨 배

Gold 5 - 구현

 

치킨과 집의 좌표들을 각 chicken과 home 리스트에 넣었다

 

일단 최대 치킨의 수를 입력 받으니깐, 치킨의 좌표를 combinations를 통해 순열을 찾는다

 

그리고 집의 기준으로 치킨 좌표들과 비교해서, 제일 가까운 거리를 찾으면 된다

 

코드

from itertools import combinations

N, M = map(int, input().split())

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

chicken, home = [], []
result = N ** N

for i in range(N):
    for j in range(N):
        if city[i][j] == 2:
            chicken.append((i, j))

        elif city[i][j] == 1:
            home.append((i, j))


for alive in combinations(chicken, M):
    distance = 0
    for h in home:
        min_distance = N * N

        for a in alive:
            dis = abs(h[0] - a[0]) + abs(h[1] - a[1])

            if dis < min_distance:
                min_distance = dis

        distance += min_distance

    result = min(distance, result)

print(result)