[BruteForce] 15686 치킨 배달

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

15686번: 치킨 배달

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

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

totalDist = 10**9 # 최종 치킨 거리
home = []
chicken = []
for i in range(n):
    for j in range(n):
        if city[i][j]==1: # 집이면
            home.append([i, j])
        elif city[i][j]==2: # 치킨 집이면
            chicken.append([i, j])
        
for chick in combinations(chicken, m): # 여러 치킨집 중 m개를 선택해 가장 가까운 집사이의 거리 구하기
    answer = 0
    for homeX, homeY in home: # 모든 집 탐색 -> 치킨집과 가장 가까운 집 구하기
        distance = 10**9
        for j in range(m): # m개의 치킨 집 -> 현재 집~치킨 집사이의 거리 구하기
            distance = min(distance, abs(homeX-chick[j][0])+abs(homeY-chick[j][1]))
        answer+=distance
    totalDist = min(answer, totalDist)

print(totalDist)

1. 집을 home리스트에 넣고 치킨 집을 chicken리스트에 좌표형태로 넣는다

2. 여러 치킨 집들 중, m개를 선택한다

3. 고른 m개의 치킨 집과 모든 집들 사이의 거리를 탐색하여 가장 짧은 거리를 구한다

4. 모든 치킨 집의 경우의 수 중, 가장 totalDist가 짧은 것을 고른다