[Python] 백준(BOJ) 15686번: 치킨 배달 - 조합, 브루트 포스

문제

15686번: 치킨 배달

풀이

조합과 브루트포스로 간단하게 풀 수 있는 문제다

import sys
from itertools import combinations
import copy

N, M = map(int, sys.stdin.readline().split(" "))
field = []
chickenhouse = []

# 인풋 받기 (0: 빈칸 / 1: 집 / 2: 치킨집)
# 치킨집 좌표는 따로 저장함
for i in range(N):
    line = list(map(int, sys.stdin.readline().split(" ")))
    for j in range(N):
        if line[j] == 2:
            chickenhouse.append([i, j])
            line[j] = 0
    field.append(line)

# 조합
com = combinations(chickenhouse, M)
result = []

# 조합 하나씩
for each in com:
    newfield = copy.deepcopy(field)
    total = 0

    # 조합에 해당하는애들만 치킨집으로 설정
    for ch in each:
        newfield[ch[0]][ch[1]] = 2

    # 돌리기
    for i in range(N):
        for j in range(N):
            # 집을 찾으면
            if newfield[i][j] == 1:
                dis = 1000
                for ch in each:
                    dis = min(dis, abs(i-ch[0])+abs(j-ch[1]))

                total += dis

    result.append(total)

print(min(result))