[알고리즘] 피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용)

(문제) 피자 배달 거리(삼성 SW역량평가 기출문제 : 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개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.

테스트케이스

입력예제	출력예제
4 4 0 1 2 0 1 0 2 1 0 2 1 2 2 0 1 2	6
5 3 0 2 0 1 2 1 2 1 0 0 0 0 0 2 0 2 0 2 0 1 1 0 0 2 0	7
10 7 0 2 0 0 0 0 0 0 1 1 2 0 0 0 1 0 1 0 0 0 0 2 0 0 0 0 2 0 1 0 0 0 0 1 1 0 0 0 0 0 2 0 0 0 2 0 0 2 0 0 0 1 0 2 0 2 0 0 0 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	22

---

해결방법

m개의 피자집이 만들어 질 수 있는 좌표를 모두 구하면서 도시와의 거리를 측정하면 최소의 값을 찾아낸다.

1. 도시와 피자집의 좌표를 각각 저장할 수 있는 리스트를 생성하여 지도상에서 전체 순회를 통해 각각의 리스트에 도시, 피자집 좌표를 append 한다.
2. dfs를 통해 피자집 좌표를 저장하는 리스트에서 m 개 만큼만 남을 수 있도록 모든 경우를 알아 본다.
3. 만약 dfs를 통해 m 개의 피자집 좌표가 저장 되어있는 리스트를 찾으면 도시의 리스트에 있는 모든 도시 좌표들과 m 개 저장 되어있는 피자집 좌표 리스트의 좌표들과 각각 거리를 측정하여 그 거리를 각 도시를 나타내는 딕셔네리로 만들어 전부 저장한다.
   (저장을 안하고, 따로 가장 작은 것만 저장하는 변수안에 넣을 수 있기는 하지만 확인을 위해 딕셔네리에 넣었다.)
4. 모든 도시들 기준으로 저장을 했을 경우 그 딕셔너리 안에 있는 거리들 중 가장 짧은 것들 끼리 더해서 min 이라는 변수와 비교하여 min 보다 작을 경우 해당 min을 그 거리로 바꾼다.
5. 이 과정을 모든 m개의 피자집을 만들 수 있는 경우에 수에 반복하여 적용하고, 끝날 때 min이라는 것을 출력한다.

---

코드

import copy
# L 피자집의 개수만 큼만 깊이 들어가기
def dfs(L):
    global _min
    # 피자들 개수 까지
    if L == len(pizzas):
        # 만약 m 개의 피자집만 존재할 경우
        if len(copy_pizzas) - copy_pizzas.count(0) == m:
            # 도시와 피자와의 거리를 전부 더한다
            # 도시와 피자집을 기억하기 위한 딕셔너리를 생성
            a = dict()
            # 각 도시들 중에서 가장 작은 거리 끼리 더하기 위한 변수
            total = 0
            # 도시에서 피자집까지 가는 모든 경우의 길이를 딕셔너리에 저장
            for i in range(len(citys)):
                for j in range(len(pizzas)):
                    # 0이 아닐 경우에만 저장
                    if copy_pizzas[j] != 0:
                        if a.get(i):
                            a[i].append(abs(citys[i][0] - copy_pizzas[j][0]) + abs(citys[i][1] - copy_pizzas[j][1]))
                        else:
                            a[i] = [abs(citys[i][0] - copy_pizzas[j][0]) + abs(citys[i][1] - copy_pizzas[j][1])]
            # 저장한 길이의 짧은 것들만 더한다
            for x in a.values():
                total = total + min(x)
            if total < _min:
                _min = total
        return
    else:
        copy_pizzas[L] = pizzas[L]
        dfs(L + 1)
        
        copy_pizzas[L] = 0
        dfs(L + 1)
        

n, m = map(int, input().split())

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

citys = []
pizzas = []

for i in range(n):
    for j in range(n):
        # 1(도시) 의 위치를 찾는다
        if maps[i][j] == 1:
            citys.append((i, j))
        # 2(피자집) 의 위치를 찾는다
        elif maps[i][j] == 2:
            pizzas.append((i, j))

_min = 2147000000

copy_pizzas = [0] * len(pizzas)

dfs(0)

print(_min)