피자 배달 거리 (DFS)

생성일: 2022년 2월 20일 오후 8:48

구현 코드

# 피자 배달 거리 (DFS)
import sys
from itertools import combinations
sys.stdin = open("input.txt", "rt")

def minDis(p, x, y):
    min = 2147000000
    for store in p:
        dis = abs(store[0]-x) + abs(store[1]-y)
        if dis < min:
            min = dis
    return min

if __name__ == "__main__":
    n, m = map(int, input().split())
    board =  []
    for _ in range(n):
        board.append(list(map(int, input().split())))

    pizza = []
    for i in range(n):
        for j in range(n):
            if board[i][j] == 2:
                pizza.append((i,j))

    c = list(combinations(pizza, m))
    res = []
    for p in c:
        tot = 0
        for i in range(n):
            for j in range(n):
                if board[i][j] == 1:
                    tot += minDis(p, i, j)
        res.append(tot)
    
    print(min(res))

모범 답안

import sys
sys.stdin=open("input.txt", "r")
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)

차이점

• 내가 구현한 코드에서는 피자 가게들의 조합을 파이썬의 itertools의 combinations을 import하여 편리하게 구하였다. (실전에서 해당 패키지를 사용하지 못할 수도 있기 때문에 직접 DFS로 조합을 구하는 방법 또한 숙지해야 한다.)
• 모범 답안에서는 피자 가게의 좌표 뿐만아니라 집들의 좌표도 리스트에 저장하여 이중 for문을 한번만 돌아도 문제를 풀 수 있도록 짜여져있다.