3️⃣ M개수만큼의 치킨집을 골랐을 때 최솟값을 찾아야하므로 M개의 치킨집을 고르는 조합의 수를 구합니다.
4️⃣ 조합의 수를 구하기위해 브루트포스와 백트래킹 알고리즘을 사용합니다.
5️⃣ dfs 재귀를 반복하면서 조건에 충족됐을 때 집과 치킨집과의 거리를 저장합니다.
6️⃣ 저장한 치킨집과의 거리를 min함수로 저장해서 최솟값을 출력합니다.
전체 코드
from sys import stdin as s
s=open('input.txt','rt')
def dfs(cur,arr):
global answer
# arr의 길이가 M과 같으면 아래 조건문 진입
if len(arr) == M:
result=0
# 집의 위치와 치킨집사이의 거리를 찾아서 저장
for x,y in house:
min_dist =float('inf')
for ix,iy in arr:
dist = abs(x-ix)+abs(y-iy)
min_dist = min(min_dist,dist)
result+=min_dist
answer = min(answer,result)
return
if cur == len(chicken):
return
# 주진 M의 개수만큼 chicken값을 arr에 추가
dfs(cur+1, arr+[chicken[cur]])
# 백트래킹
dfs(cur+1, arr)
if __name__=='__main__':
N,M =map(int,s.readline().split())
arr = [list(map(int,s.readline().split())) for _ in range(N)]
answer=float('inf')
chicken =[]
house=[]
# 집의 위치와 치킨집의 위치를 찾아서 큐에 저장
for i in range(N):
for j in range(N):
if arr[i][j]==1:
house.append((i,j))
if arr[i][j]==2:
chicken.append((i,j))
dfs(0,[])
print(answer)