🥇[백준] 15686 치킨 배달 (골드5) / 구현, 백트래킹

문제요약

나의 코드 및 설명

• 백트래킹을 활용하여 가능한 m개의 치킨집 좌표 케이스들을 저장하고, 하나씩 탐색하며 최단 치킨거리를 찾는다. 

#백트래킹으로 폐업시키지 않을 치킨집 구하기
def dfs(count, start, temp_list):
    if len(temp_list) == m: #m개가 되면,
        result.append(temp_list) #result에 저장된 리스트 저장 후 리턴
        return
    
    for i in range(start, len(chicken)):
        if i not in v:
            v.append(i)
            dfs(count+1, i+1, temp_list+[chicken[i]])
            v.pop()


n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

chicken = [] #전체 치킨집의 좌표를 담는다.
result = [] #폐업하지 않은 치킨집 케이스들

#전체 치킨집 저장
for i in range(n):
    for j in range(n):
        if board[i][j] == 2:
            chicken.append((j,i)) 

v = []
dfs(0,0,[]) #m개의 치킨집 좌표를 고르는 백트래킹 함수 실행

ans = [] #폐업하지 않은 치킨집 좌표를 탐색하며 각 케이스별 최단 치킨거리를 저장한다.

for k in result: #치킨집 좌표를 하나씩 꺼내면서 살펴본다.
    total = 0
    for y in range(n):
        for x in range(n):
            if board[y][x] == 1: #집인 곳의 좌표를 찾으면
                distance = 1000
                for c in k: #폐업하지 않은 치킨집 좌표 중 가까운 치킨 거리를 찾는다.
                    if distance > abs(x-c[0]) + abs(y-c[1]):
                        distance = abs(x-c[0]) + abs(y-c[1])
                total += distance #치킨 거리의 총 합을 구한다.
    
    ans.append(total)
                
print(min(ans))

피드백

처음에는 집을 기준으로 가까운 치킨집을 찾으려했는데 백트래킹으로 어떻게 구현할까 막막했다.. 2차원 배열에서의 백트래킹은 연습이 안되어있었기 때문이다. 그러던 중 백트래킹을 활용하여 m개의 치킨집 좌표를 구하고 저장된 좌표들을 하나씩 꺼내어 치킨거리를 구하는 방식으로 문제를 해결하면 되겠다 싶었고, 문제를 해결할 수 있었다. 문제의 접근 방식에 있어서 유연함을 가져야겠다. 배울게 많았던 문제. 다음에 다시 한 번 더 풀어봐야겠다.