취준/백준
[백준][Python][15686][브루트포스] 치킨 배달
puff
2020. 3. 3. 08:04
문제 : 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))