[BOJ] 15686번 치킨배달 / 사용언어 : 파이썬(python)

※ 문제링크

15686번: 치킨 배달

해당문제는 DFS와 백트래킹으로 풀 수 있는 문제였다. 모든 경우의 수를 탐색해야하기에 브루스포트 알고리즘으로도 볼 수 있는 문제였으며, 간단하게 풀이방법을 설명하면 DFS와 백트래킹을 이용하여 치킨집이 존재할 수 있는 모든 경우의수(조합)을 구하고 문제에서주어진 거리 공식을 활용하여 거리를 계산하여 최솟값을 출력하면 되는 문제였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 바탕으로 치킨상점과 집의 최초 위치를 기록할 필드를 2차원 배열로 구현한다.

2. 2중 반복문을 통해 치킨상점과 집의 좌표를 리스트에 저장한다.

3. DFS함수를 활용하여 M개의 치킨상점이 있을 수 있는 모든 경우의 수를 구하여 저장한다.

4. 3중 반복문을 활용하여 치킨상점과 집의 거리를 모두 계산하여 최종적으로 가장 짧은 거리를 출력한다.

+ 메모리 및 시간단축을 위해 sys를 사용하였습니다.

(사실 BFS로 완전탐색을 해도 같은 결과값은 나오나 시간초과가 뜨니 참고하시기 바랍니다.)

 

import sys
# input = sys.stdin.readline
N, M = map(int, input().split())
field = []
for _ in range(N):
    field.append(list(map(int, input().split())))

store_loc = []
house_loc = []
for x in range(N):
    for y in range(N):
        if field[y][x] == 1:
            house_loc.append([x, y])
        if field[y][x] == 2:
            store_loc.append([x, y])

visited = [False for _ in range(len(store_loc))]
arr = []
cases = []
# dfs와 백트래킹으로 치킨집이 있을 수 있는 위치 확인 후 저장
def check_cases(start):
    if len(arr) == M:
        cases.append(arr.copy())
        return

    for i in range(start, len(store_loc)):
        if visited[i]:
            continue

        arr.append(store_loc[i])
        visited[i] = True
        check_cases(i+1)
        arr.pop()
        visited[i] = False

check_cases(0)

ans = float('inf')
for i in range(len(cases)): 
    dt_cd = 0
    for house in house_loc:     
        distance = float('inf')  
        for case in cases[i]:
            tt_dt = abs(house[0] - case[0]) + abs(house[1] - case[1])
            if distance > tt_dt:
                distance = tt_dt
        dt_cd += distance
    if ans > dt_cd:
        ans = dt_cd
print(ans)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.