본문 바로가기

취준/백준

[백준][Python][15686][브루트포스] 치킨 배달

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

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는

www.acmicpc.net

브루트 포스 문제다.

 

N이 <50이라 안될 거 같아도 사실 신경 써야 하는 건 치킨집의 개수고 M <=13 이므로 2^13 == 8192 정도에 N*M 이니까 combination으로 전부 탐색해도 된다.

 

그 후 거리를 구하는데, Manhattan distance(L1) 로 구해야 한다. 

 

 

집 개수랑 치킨집 개수랑 헷갈리지 말자. 

 

 

import sys
from itertools import combinations


n, m = [int(i) for i in sys.stdin.readline().split()]

arr = []
for _ in range(n):
    arr.append([int(i) for i in sys.stdin.readline().split()])
house = []
chicken = []

for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            house.append((i, j))
        elif arr[i][j] == 2:
            chicken.append((i, j))


ans = []
for p in combinations(chicken, m):
    ret = 0
    for h in house:
        minval = 991234
        for c in p:
            minval = min(abs(h[0]-c[0]) + abs(h[1]-c[1]), minval)

        ret += minval

    ans.append(ret)

print(min(ans))