풀이 특징
itertools
import combinations
# 0: 빈칸, 1: 집, 2: 치킨집
# 치킨 거리: 집과 가장 가까운 치킨집 사이의 거리
# 도시의 치킨 거리: 모든 집의 치킨 거리의 합
# 최대 M개의 치킨집을 골랐을 때 도시의 치킨 거리의 최솟값
from itertools import combinations
def dist(a, b):
return abs(b[0] - a[0]) + abs(b[1] - a[1])
NONE, HOUSE, CHICK = 0, 1, 2
n, m = map(int, input().split())
house = []
chick = []
for r in range(n):
row = list(map(int, input().split()))
for c in range(n):
if row[c] == HOUSE:
house.append((r, c))
elif row[c] == CHICK:
chick.append((r, c))
# 도시의 치킨 거리 최솟값
minDist = int(1e9)
for case in list(combinations(chick, m)):
# 선택된 m개의 치킨집기준 도시의 치킨 거리 최솟값
distSum = 0
for a in house:
# 특정 집의 치킨 거리 최솟값
houseDist = int(1e9)
for b in case:
temp = dist(a, b)
houseDist = min(houseDist, temp)
# 특정 집의 치킨 거리 최솟값이 구해지면 도시의 치킨 거리 최솟값에 반영
distSum += houseDist
# 선택된 m개의 치킨집기준 도시의 치킨 거리 최솟값이 구해지면 도시의 치킨 거리 최솟값에 반영
minDist = min(minDist, distSum)
print(minDist)
from itertools import permutations
def solution(n, weak, dist):
# 취약 지점 개수
length = len(weak)
# 원형을 길이 2배로 늘린 일자형태로 변형
for i in range(length):
weak.append(weak[i] + n)
# 투입할 친구수 초기값은 친구수+1
answer = len(dist) + 1
# 취약지점 시작점
for start in range(length):
# 친구들 순서나열
for friends in list(permutations(dist, len(dist))):
# 투입할 친구수
count = 1
# 점검할 수 있는 마지막 위치 = 취약지점 + 가능길이
position = weak[start] + friends[count - 1]
# 시작점부터 모든 취약한 지점을 확인
for index in range(start, start + length):
# 범위를 벗어난 경우
if weak[index] > position:
# 새로운 친구 투입
count += 1
# 더 투입이 불가한 경우 종료
if count > len(dist):
break
# 점검할 수 있는 마지막 위치 = 현재 취약지점 + 가능 길이 업데이트
position = weak[index] + friends[count - 1]
# 취약가능한 모든지점을 살펴본 후 최소값 업데이트
answer = min(answer, count)
# 모든 친구 투입에도 불가한 경우
if answer > len(dist):
return -1
return answer