import sys
input = sys.stdin.readline
from collections import deque
N,M = map(int,input().split())
Map = []
house = []
chicken = []
for i in range(N):
Map.append(list(map(int,input().split())))
for i in range(N):
for j in range(N):
if Map[i][j] == 1:
house.append((i,j))
elif Map[i][j] == 2:
chicken.append((i,j))
Nchicken = len(chicken)
housechicken = []
for i in house:
housechicken.append([])
for j in chicken:
yh,xh = i
yc,xc = j
housechicken[-1].append(abs(yh-yc)+abs(xh-xc))
delchicken = []
distancecity = 0
for i in housechicken:
distancecity += min(i)
delcount = Nchicken-M
dq = deque()
def Pick(x):
if len(dq) == delcount:
delchicken.append(tuple(dq))
for i in range(Nchicken):
if i > x:
dq.append(i)
Pick(i)
dq.pop()
Pick(-1)
if delcount != 0:
distancecity = 1000000
for delnum in delchicken:
distancecity_del = 0
for i in housechicken:
distance = 100
for j in range(Nchicken):
if j in delnum:
continue
if i[j] < distance:
distance = i[j]
distancecity_del += distance
distancecity = min(distancecity,distancecity_del)
print(distancecity)
재귀함수를 이용해서 삭제할 치킨집 개수의 조합을 delchicken 리스트에 튜플로 저장하고, 튜플을 불러오는 방법을 사용했다.
다른 사람들의 풀이에 비해 코드의 길이가 긴편인데, 다른 사람들의 한 방식을 보니 특별히 다른점은 없는데 한가지 차이점이라면 다른 사람들은 재귀함수가 아닌 itertools라는 아주 편리한 기능을 이용해서 조합을 구했다는 것이었다.
비슷한 문제가 나온다면 itertools를 이용해야겠다.
오늘의 교훈: itertools 이용하기