[Python 3] BOJ - 15686 "치킨 배달"

 # 문제 링크 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

 # 풀이 :

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)