BOJ
[Python 3] BOJ - 15686 "치킨 배달"
PeiSea
2020. 3. 24. 21:07
# 문제 링크 : https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는
www.acmicpc.net
# 풀이 :
N,M 제한이 작으므로 브루트 포스를 이용하여 접근하였다. 총 N개의 치킨집 중 M개만 남기고 모두 제거해야하므로 N - M개의 치킨집을 골라야 한다. 순서에 따른 의미의 변화가 없으므로 순열보다는 조합을 이용하였다. 따라서 모든 경우에 대해 남아있는 치킨집과 일반 가정의 치킨 거리의 합을 모두 구하고, 그 떄 마을의 치킨 거리의 총합의 최소를 구하면 된다.
# 코드
import sys, itertools
# 입력부
n,m = map(int, sys.stdin.readline().split())
town = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
home = []
chicken = []
for i in range(n):
for j in range(n):
if town[i][j] == 1:
home.append((i,j))
elif town[i][j] == 2:
chicken.append((i,j))
# dist : 집(a,b)와 치킨집(c,d)간의 치킨거리를 리턴하는 함수
def dist(a,b,c,d):
return abs(a-c) + abs(b-d)
ans = 99999999999999999999999
# delete = N-M개의 치킨집을 제거하는 조합 리스트
delete = list(itertools.combinations(chicken, len(chicken) - m))
for k in delete:
idx = 0
# min_dist : 각 집을 기준으로 각 치킨집과의 치킨 거리중 가장 작은 거리를 저장
min_dist = [0] * len(home)
for i in home:
temp = []
for j in chicken:
# 원래 치킨집인데 delete에 있으면 건너뜀
if j in k:
continue
# 치킨 거리 계산
each = dist(i[0],i[1],j[0],j[1])
temp.append(each)
# idx번째 집의 치킨 거리들 중 가장 작은 치킨 거리
min_dist[idx] = min(temp)
idx += 1
# sum(min_dist)는 k번째 조합일때 마을의 총 치킨거리이므로 ans와 비교 후 최소값 갱신
if ans > sum(min_dist):
ans = sum(min_dist)
print(ans)