Algorithm - 피자 배달거리(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[피자 배달거리(DFS)]

 

N x N 크기의 도시 지도가 있다.

도시지도는 1 x 1 크기의 격자칸으로 이루어져 있으며, 각 격자칸에서 0은 빈칸, 1은 집, 2는 피자집으로 표현된다.

각 격자칸은 좌표(행 번호, 열 번호)로 표현되며, 행 번호는 1번부터 N번까지이고 열 번호도 1부터 N까지이다.

도시에는 각 집마다 "피자 배달거리"가 있는데 각 집의 피자 배달거리는 해당 집과 도시의 존재하는 피자집들과의 거리 중 최소값을 해당 집의 "피자 배달거리"라고 한다. 참고로, 집과 피자집의 피자 배달거리는 " |x1-x2| + |y1-y2| " 이다.

 

예를 들어, 도시지도가 아래와 같다면 좌표 (0, 1)에 있는 집과 좌표 (1, 2)에 있는 피자집 사이의 피자 배달거리는 |0-1| + |1-2| = 2가 된다.

 

4 * 4 도시지도

 

최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있다.

해당 도시의 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주며 폐업시키려고 한다.

시장이 피자집 M개를 선택하는 기준은 " 도시의 피자 배달거리가 최소가 되는 M개의 피자집 "이다.

참고로, 도시의 피자 배달거리는 각 집들의 피자 배달거리를 모두 합한 것이다.

 

위의 모든 조건을 고려하여 도시지도가 입력값으로 주어졌을 때, 도시의 '최소 피자 배달거리'를 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.

두 번째 줄부터 도시 정보가 입력된다.

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_72.txt', 'rt')

def DFS(L, s):
    global res
    if L == m:
        sum = 0
        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)
            
if __name__ == "__main__":
    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)
    
# 출력 : 6

 

input_72.txt(입력)

4 4
0 1 2 0
1 0 2 1
0 2 1 2
2 0 1 2

 

 

중요내용

1. 피자집 n개 중 4개를 임의로 선택하는 방식(조합)으로 DFS 탐색이 진행된다. [조합 문제와 동일한 원리 사용]
2. 리스트 board에는 도시의 지도 정보가 저장된다.
3. 리스트 hs에는 하우스의 위치정보가 저장된다.
4. 리스트 pz에는 피자집의 위치정보가 저장된다.
5. 리스트 cb에는 n개의 피자집 중 임의로 선택된 4개의 피자집 정보가 저장된다. (즉, 조합의 경우의수를 저장함)
6. 변수 dis에는 특정 집과 선택된 4개의 피자집 간의 최소 배달거리가 저장된다.
7. 변수 sum에는 조합으로 선택된 4개의 피자집과 모든 집들 간의 최소 배달거리를 구하여 모두 더한 값이 저장된다. (즉, 도시 피자배달거리가 저장됨)
8. 변수 res에는 도시 피자 배달거리의 최소값이 저장된다. (즉, sum의 최소값이 저장됨)
9. DFS() 함수의 인자 L은 상태트리의 레벨을 의미하며, 동시에 리스트 cb에 접근하는 인덱스 번호로 사용된다.
10. DFS() 함수의 인자 s는 상태트리의 간선을 의미한다. (즉, 조합으로 선택되는 피자집의 번호를 의미함)
11. 변수 x1, y1은 집의 좌표를 의미하고, 변수 x2, y2는 피자집의 좌표를 의미한다.