[김태원 알고리즘] 피자 배달 거리 (DFS)

사용 언어: Python3

문제

풀이

import sys
sys.setrecursionlimit(10**6)

def calcDist(pizza):
    # ✅ 집 하나를 고정해두고, 도시에 있는 모든 피자집까지 거리 계산
    global ans
    tot = 0
    for x in house: # 도시에는 "각 집마다" 피자배달거리가 있는데...
        mn = 2147000000
        for y in pizza:
            mn = min(mn, abs(x[0]-y[0]) + abs(x[1]-y[1])) # 해당 집과 도시에 존재하는 피자집들과의 거리 중 "최소값"을 해당 집의 피자배달거리라고 한다
        tot += mn
    ans = min(tot, ans)

# 피자집들 중 M개 뽑기
def DFS(L, start):
    if L == M:
        calcDist(res)
    else:
        for i in range(start, pzSize):
            if visited[i]:
                continue
            res[L] = pizza[i]
            visited[i] = 1
            DFS(L+1, i+1) # start는 i+1
            visited[i] = 0

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

house, pizza = [], []
for i in range(N):
    for j in range(N):
        if board[i][j] == 1:
            house.append((i, j))
        elif board[i][j] == 2:
            pizza.append((i, j))

res = [tuple()] * M # pizza 집 중 M개 선택하는 조합의 경우의 수
pzSize = len(pizza) # pizza size
visited = [0] * pzSize

ans = 2147000000
DFS(0, 0)
print(ans)

• 문제를 잘못 이해해서 오답이 나왔었다. 문제를 꼼꼼히 잘 읽자..
  • 각 집의 피자배달거리는 그 집에서부터 도시 안에 있는 모든 피자집까지 거리의 최소값이다.
  • 도시의 피자배달거리는 각 집들의 피자배달거리를 합한 것을 말한다.
  • 문제에서 구하는 것은 도시의 피자배달거리가 최소가 되는 M개의 피자집이 선택되었을 때, 도시의 최소 피자배달거리를 출력하는 것이다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기