백준 - 치킨 배달 (완전 탐색) / Gold 5 / 15686번

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

15686번: 치킨 배달

 

풀이

import sys
from itertools import combinations


def calculate(stores):
    result = 0
    for k in home:
        result += min([abs(l[0] - k[0]) + abs(l[1] - k[1]) for l in stores])

    return result


n, m = map(int, sys.stdin.readline().split())

answer = []
table = []
store = []
home = []

for _ in range(n):
    table.append(list(map(int, sys.stdin.readline().split())))

for i in range(n):
    for j in range(n):
        if table[i][j] == 2:
            store.append([i, j])
        elif table[i][j] == 1:
            home.append([i, j])

close = len(store) - m
targets = list(combinations(store, close))

for target in targets:
    temp = store[:]  # 재할당할땐 복사본으로. (그렇지 않으면 temp과 store가 같은 메모리 주소를 공유하기 때문에 둘다 바뀜)
    for i in target:
        temp.remove(i)
    answer.append(calculate(temp))

print(min(answer))

이 문제도 N의 크기를 확인하여 완전 탐색이 가능한지 판단해야 한다.

N의 최대 크기가 50이고 치킨집의 수도 최대 13이기 때문에 폐업할 집을 선택하는 조합의 수을 감안하더라도

완전 탐색으로 풀어도 되겠다는 판단을 했다.

 

1이 존재하는 [행 번호, 열 번호] , 2가 존재하는 [행 번호, 열 번호] 형태로 관리하여

쉽게 최소거리를 판단할 수 있었다.