[Python Algorithm] 깊이/넓이 우선탐색(DFS, BFS) - 피자 배달 거리(DFS)

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (DFS 편)

 

 

 

 

 

📖 문제 : 피자 배달 거리

N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호) 로 표현됩니다. 행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.
도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재 하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.

집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다. 예를 들어, 도시의 지도가 아래와 같다면

(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다. 최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다. 도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.
시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다.
도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.

 

 

 

입력설명
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다. 둘째 줄부터 도시 정보가 입력된다.

 

출력설명
첫째 줄에 M개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.

 

입력예제 1

4 4
0 1 2 0

1 0 2 1

0 2 1 2

2 0 1 2

 

출력예제 1

6

 

 

import sys
input = sys.stdin.readline

def DFS(L, s):
  global res
  if L==m:
    sum = 0
    # for x in cb:
    #   print(x, end =' ')
    # print()
    for j in range(len(hs)):
      x1 = hs[j][0]
      y1 = hs[j][1]
      dis = 2147000000
      for x in cb:
        x2 = pz[x][0]
        y2 = pz[x][1]
        dis = min(dis, abs(x1 - x2)+abs(y1-y2))
      sum+=dis
    if sum<res:
      res=sum

  else:
    for i in range(s, len(pz)):
      cb[L] = i
      DFS(L+1, i+1)
    


n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
hs = []
pz = []
cb = [0]*m
res = 2147000000

for i in range(n):
  for j in range(n):
    if board[i][j] == 1:
      hs.append((i,j))
    elif board[i][j] == 2:
      pz.append((i,j))

DFS(0, 0)
print(res)

 

⭐️ Point ! ⭐️

• section 5에서 배운 조합 ! 여기서 또 써먹네 (주석처리 풀어보면 조합의 결과 출력 위의 경우 6C4)
  
  

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이