백준 15686 치킨 배달 / python

문제 : 15686

풀이 point

치킨집 중 M개를 뽑는 경우의 수를 모두 만들어서 집들과 치킨 집의 거리를 비교한 후 가장 작은 치킨집 거리를 구한다.

풀이 방법

경우의 수는 백트래킹을 활용하여 구할 수 있다. (파이썬의 경우 라이브러리 함수가 존재)
그 후 집마다 경우의 수에서 고른 치킨집까지의 거리 중 가장 최소값만을 구한 후 경우의 수들 중 가장 치킨 거리가 최소가 되는 값을 구한다.

풀이 코드

N, M = map(int, input().split())



grid = [list(map(int, input().split())) for _ in range(N)]

home = []
chicken = []

for i in range(N):
  for j in range(N):
    if grid[i][j] == 1:
      home.append([i, j])
    elif grid[i][j] == 2:
      chicken.append([i, j])

visit = [False]*(len(chicken))

ans = 9999999
def back(start, depth):
  global ans
  if depth == M:
    tmp = 0
    for h in home:
      dist = 9999999
      for i in range(len(chicken)):
        if visit[i]:
          d = abs(chicken[i][0]-h[0])+abs(chicken[i][1]-h[1])
          dist = min(dist, d)
      tmp += dist
    
    ans = min(ans, tmp)
    return
  
  for i in range(start, len(chicken)):
    if visit[i]: continue

    visit[i] = True
    back(i+1, depth+1)
    visit[i] = False

back(0, 0)

print(ans)