[인프런] 피자 배달 거리

---

문제설명

N by N 크기의 도시지도가 있다. 도시지도는 1 by 1 크기의 격자칸으로 이루어져 있다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현된다. 각 격자칸은 좌표(행번호, 열번호)로 표현된다. 행,열 번호 모두 1부터 N번까지 이다.

도시에는 각 집마다 '피자배달거리'가 있는데, 각 집의 피자배달거리는 해당 집과 도시에 존재하는 피자집들과의 거리 중 최솟값을 해당 집의 '피자배달거리'라고 한다. 집과 피자집의 피자배달거리는 $|x_1 -x_2| + |y_1 - y_2| $이다.

 

 

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

입력조건

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

출력조건

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

사고과정

• 역시 삼성 문제라.. 문제를 꼼꼼히 읽느라 시간이 꽤 걸렸다. 처음에 문제를 풀 때 최소가 되는 M값이 이미 제시된다는 것을 보고 피자집 좌표 중에 M개를 선택하는 조합을 구하고 이 조합들 중 가장 최소의 도시 피자배달거리를 구하면 되었는데... 이를 캐치하지 못했다.
• 오히려 이전까지 좌표를 직접이동하는 DFS 탐색 문제만 푸느라 그랬는지.. 이 문제도 그런 관점으로 접근했다. 하지만 그렇게 할 필요 없이 한 번 선형탐색 돌면서 집, 피자집 좌표들을 담아놓고 피자집 좌표들 중 M개를 고르는 조합을 DFS 탐색으로 구한 후, 개별 조합을 구할 때마다 도시의 피자배달거리를 구하면서 최솟값을 갱신하면 되었다..
• 풀이에서 아이디어만 보고 구현을 시도했는데, 생각보다 쉽게 구현했다.. 아쉽다 ㅜ,ㅜ
• 그리고 직접 구현한 풀이에서 M개를 뽑은 조합을 빈리스트에 append하고 백트레킹할 때 pop하는 식으로 구현했지만 강의 속 풀이에는 애초에 M 사이즈의 리스트를 정의하고 각 원소값에 피자집 좌표를 넣는 방식으로 구현했다

풀이(스스로 못 푼 풀이)

- 나의 풀이

n, m = map(int, input().split())
house = []
pizza = []
for i in range(n):
    data = list(map(int, input().split()))
    for j in range(n):
        if data[j] == 1:
            house.append((i, j))
        if data[j] == 2:
            pizza.append((i, j))

def dfs(L, idx, res: list):
    global answer
    # 한 조합의 경우 당 계산
    if L == m:
        city_dist = 0
        for h_x, h_y in house:
            dist = int(1e8)
            for p_x, p_y in res:
                dist = min(dist, abs(h_x-p_x)+abs(h_y-p_y))
            city_dist += dist
        answer = min(answer, city_dist)
    else:
        for i in range(idx, len(pizza)):
            res.append(pizza[i])
            dfs(L+1, i+1, res)
            res.pop() # 백트레킹 위해 pop

answer = int(1e9)
res = []
dfs(L=0, idx=0, res=res)
print(answer)

- 강의 풀이

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
hs = pz = []
cb = [0] * m
res = int(1e9)
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))


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


DFS(0, 0)
print(res)