Part6.17_완전탐색_깊이,넓이 우선탐색활용_피자 배달 거리(DFS)

피자 리스트와
집 리스트를 만든다

선생님 코드

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