[Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-피자 배달 거리(DFS 활용)

 

 

• 일단 피자집 M개가 선택되어야 하는 상황이니 조합을 생각했어야 한다! 예를 들어, 6개 중 4개만 뽑는다 하면 DFS를 사용하여 4가지만 뽑는 경우의 수를 구할 수 있다 
• 그리고 뽑아진 M개의 피자집을 가지고 집들을 모두 for문을 이용하여 돌면서 하나의 집당 어떤 피자집과 가장 최소거리를 갖는지 찾은 후, 그 거리들을 모두 더하면 최소 피자배달거리가 나온다
• 나온 최소 피자배달거리도 조합에 따라 모두 다를 것이다. 그 중에 가장 최소값을 찾으면 되는 문제인 것이다 

def DFS(level, start):
 
    global res
 
    if level == m:
        sum = 0
        for i in range(len(house)):
            x, y = house[i][0], house[i][1]
            dist = 2147000000
            for z in combination:
                x2, y2 = pizza[z][0], pizza[z][1]
                dist = min(dist, abs(x-x2) + abs(y-y2))
 
            sum += dist
        if sum < res:
            res = sum
 
    else:
        for j in range(start, len(pizza)):
            combination[level]=j
            DFS(level+1, j+1)
 
 
if __name__=='__main__':
 
    n, m = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
 
    pizza = []
    house = []
    combination = [0]*m
    res = 2147000000
 
    for i in range(n):
        for j in range(n):
            if board[i][j]==2:
                pizza.append((i,j))
            elif board[i][j]==1:
                house.append((i,j))
    DFS(0, 0)
    print(res)