[백준] 15686 치킨 배달 [python]

 

 

문제 풀이

1️⃣ 치킨집의 위치와 집의 위치를 미리 찾아서 리스트에 저장합니다.

2️⃣ 치킨집과의 최솟값을 찾아야하므로 변수를 max사이즈로 지정해줍니다.

3️⃣ M개수만큼의 치킨집을 골랐을 때 최솟값을 찾아야하므로 M개의 치킨집을 고르는 조합의 수를 구합니다.

4️⃣ 조합의 수를 구하기위해 브루트포스와 백트래킹 알고리즘을 사용합니다.

5️⃣ dfs 재귀를 반복하면서 조건에 충족됐을 때 집과 치킨집과의 거리를 저장합니다.

6️⃣ 저장한 치킨집과의 거리를 min함수로 저장해서 최솟값을 출력합니다.

 

 

전체 코드

from sys import stdin as s
s=open('input.txt','rt')

def dfs(cur,arr):
    global answer
    
    # arr의 길이가 M과 같으면 아래 조건문 진입
    if len(arr) == M:
        result=0
        # 집의 위치와 치킨집사이의 거리를 찾아서 저장
        for x,y in house:
            min_dist =float('inf')
            for ix,iy in arr:
                dist = abs(x-ix)+abs(y-iy)
                min_dist = min(min_dist,dist)
            result+=min_dist
        answer = min(answer,result)
        return
        
    
    if cur == len(chicken):
        return
    # 주진 M의 개수만큼 chicken값을 arr에 추가
    dfs(cur+1, arr+[chicken[cur]])
    # 백트래킹
    dfs(cur+1, arr)
        
if __name__=='__main__':
    N,M =map(int,s.readline().split())
    arr = [list(map(int,s.readline().split())) for _ in range(N)]
    answer=float('inf')
    chicken =[]
    house=[]
    
    # 집의 위치와 치킨집의 위치를 찾아서 큐에 저장
    for i in range(N):
        for j in range(N):
            if arr[i][j]==1:
                house.append((i,j))
            if arr[i][j]==2:
                chicken.append((i,j))
    dfs(0,[])
    print(answer)