[백준 - Python] 15686. 치킨 배달 (완전 탐색)

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

15686번: 치킨 배달

 

코드

from itertools import combinations
import sys
input =  sys.stdin.readline

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

house = []
chicken = []
# 집, 치킨집 위치 저장
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            house.append((i+1, j+1))
        if city[i][j] == 2:
            chicken.append((i+1, j+1))

result = []
# m개의 치킨집 선택
per = list(combinations(chicken, m))
for i in range(len(per)):
    dist = 0
    for k in range(len(house)):
        tmp = 101
        for j in range(m):
            tmp = min(tmp, abs(per[i][j][0] - house[k][0]) + abs(per[i][j][1] - house[k][1]))
        dist += tmp
    result.append(dist)

print(min(result))

 

어떤 집에서의 치킨 거리는

그 집과 가장 가까운 치킨집 사이의 거리이다.

처음에 모든 치킨집까지의 거리 합을 치킨 거리라 생각하고 풀어서 좀 헤맸다.

 

문제에서 주어지는 정의를 확실하게 알고 풀자 !

 

집과 치킨집의 좌표값을 각각 리스트로 저장하고

조합 라이브러리를 활용해

M개의 치킨집을 선택할 수 있는 경우의 수를 모두 살펴보며, 도시의 치킨 거리의 최솟값을 구했다.

 

2차원 배열을 돌면서

배열에 저장된 값들이 의미하는 바에 따라

좌표 값을 튜플 형태로

다른 1차원 리스트에 저장해 관리하는 구현법을 눈여겨 봐두면 좋을 것 같다!