[파이썬 PYTHON] 백준 15686번 【치킨 배달】

---

import sys

#예제 입력
N,M = map(int,sys.stdin.readline().split())
_map = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]

chickens = []
houses = []

# 집과 치킨집 좌표 저장
for row in range(N):
    for col in range(N):
        if _map[row][col] == 2:
            chickens.append([row,col])
        elif _map[row][col] == 1:
            houses.append([row,col])

selected = []
checked = [False]*(len(chickens))
ans = 1e9

def getMinDistance(selected):
    minDistance = 0
    for house in houses:
        houseR = house[0]
        houseC = house[1]
        distance = 1e9
        for storeNum in selected:
            chicken = chickens[storeNum]
            chickenR = chicken[0]
            chickenC = chicken[1]
            distance = min(distance,abs(houseR-chickenR)+abs(houseC-chickenC))
        minDistance +=distance
    return minDistance
    
def bt():
    global ans
    if len(selected) == M:
        ans = min(ans,getMinDistance(selected))
        return
    for i in range(len(chickens)):
        if checked[i] == True:
            continue
        if len(selected)>=1 and selected[-1] > i:
            continue
        selected.append(i)
        checked[i] = True
        bt()
        selected.pop()
        checked[i] = False
bt()
print(ans)

 

문제 접근 방법

1. 치킨 집 좌표를 배열(스택)에 넣어둔다.

2. 치킨 집을 M개 선택해서 얻을 수 있는 모든 조합을 구해야 한다.

    2.1 python의 combinations 사용

    2.2 ✔ 백트래킹 방식 사용 

3. 백트래킹으로 구한 selected 스택에는 좌표가 들어가는 것이 아닌 배열의 위치 정보가 들어감

   -> ex) 치킨집이 3개이고 2개를 선택할 수 있다면, (치킨 집 좌표 = [a,b] [c,d] [e,f]

               selected 안에는 [ [a,b],[c,d] ] / [ [a,b],[e,f] ] / [ [c,d],[e,f] ]  이런식으로 저장되는 것이 아닌

               [0,1] [0,2] [1,2] 이런식으로 저장

4. 백트래킹 시, checked 와 조건문으로 중복 선택 제거

5. 백트래킹으로 치킨집 M개를 선택했다면, 도시의 최소 치킨 거리를 getMinDistance() 함수로 구함

-> 로직 짤때 은근히 헷갈렸는데, 변수를 하나하나 풀어서 작성했더니 잘 작성할 수 있었다.