백트래킹(백준 알고리즘 1987)

♣ 백트래킹 알고리즘

현재 상태에서 가능한 모든 경로를 따라 들어가서 탐색하다가 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는 알고리즘이다(방금 왔던 길을 되돌아간다는 의미). 즉 모든 가능성을 시도하는 것이 아니라 해결책에 대한 후보군을 구성하고 그 후보군이 문제의 조건을 만족하는지의 여부를 검사하며 해답을 찾는 것이다. 

 

백트래킹은 보통 재귀함수를 이용하여 구현된다. DFS와 혼동하기 쉬운데, 백트래킹은 불필요한 탐색을 하지 않는다. 하지만 DFS는 모든 경우의 수를 자식 노드가 끝날 때까지 탐색한다. 

 

백트래킹의 특징

• 어떤 노드에서 출발하는 경로가 그 해결책으로 이어질 것 같지 않으면 더 이상 경로를 탐색하지 않음으로써 시도 횟수 감소
• 불필요한 경로의 조기 차단
• N! 가지의 경우의 수를 가진 문제에 대해 백트레킹에 가하면 일반적으로 경우의 수가 줄어들지만 최악의 경우는 처리 불가능
• 모든 후보를 검사하지 않음

 

DFS의 특징

• 모든 경로를 추적
• N! 가지의 경우의 수를 가진 문제에 대해 깊이 우선 탐색을 이용하면 처리 불가능
• 모든 후보를 검사

 

 

♣ 백준 알고리즘 1987번

 

 

 

위의 문제에서는 알파벳 보드가 주어지고 좌측 상단(1행 1열)에서 말이 출발한다. 말은 상하좌우로 인접한 네 칸 중 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적힌 알파벳이 지금까지 지나온 알파벳과는 달라야 한다. 말이 최대한 몇 칸을 지날 수 있는지 구하는 문제이다. 

 

 

<입력>

 

<알파벳 보드 만들기>

 

<해당 알파벳을 지나왔는지 체크할 visited 만들기>

A부터 Z 까지의 알파벳이 있을 때(26개) 각 알파벳을 지날 때마다 visited를 True로 바꾼다. 

 

 

<깊이우선탐색 알고리즘 만들기>

 

dfs 알고리즘에는 x, y, visited, depth가 주어진다. x와 y는 현재 말이 있는 칸의 위치를 의미한다. x는 가로 칸, y는 세로 칸이다. 또한 dist는 지나간 알파벳의 최대 개수를 구하기 위해 정의한 변수이다. 

 

처음 말의 위치는 (0, 0)이므로 dfs(0, 0, visited, 1)을 실시한다. depth는 1로부터 시작하는데, 말이 (0, 0)에 해당하는 첫 칸은 이미 방문했기 때문에 깊이(방문한 알파벳의 수)가 1이기 때문이다. 

 

dfs(0, 0, visited, 1)을 실시하면 dfs 함수 밖에서 0으로 정의한 dist를 가져온다. 현재 depth=1, dist=0 이고, dist는 가장 큰 값을 원하기 때문에 1이 된다. 또한 n은 현재 방문하고 있는 알파벳을 의미한다. 주어진 입력에서 (0, 0)에 해당하는 알파벳은 'I' 이므로 n=I 이다. 이렇게 I는 이미 방문했기 때문에 visited를 True로 바꿔야 한다. 알파벳을 숫자로 바꿔주는 함수인 ord를 이용하여 visited[ord(n)-65]를 True로 바꾼다. 

 

adj_list는 현재 위치에서 방문할 수 있는 범위의 리스트이다. x에서 앞뒤로 1칸, y에서 앞뒤로 1칸 이동이 가능하기 때문에 현재 방문할 수 있는 위치는 [x-1, y], [x+1, y], [x, y-1], [x, y+1] 이다. 

 

말이 adj_list 범위를 하나씩 이동하도록 for문을 돌린다. px는 이동한 칸의 x 위치를, py는 이동한 칸의 y 위치를 의미한다. 

이때 이동한 칸은 양수여야 하며, r 미만이어야 하므로 이동할 수 있는 범위를 설정한다. 

 

이동한 위치가 원하는 범위에 맞으면 이동한 칸의 알파벳을 n에 넣는다. 그리고 해당 알파벳의 visited가 False인지, 즉 아직 방문하지 않은 알파벳이 맞는지 확인한다. 방문하지 않은 알파벳이 맞다면, 해당 알파벳이 현재 방문하고 있는 알파벳이 된다. 따라서 dfs(px, py, visited, depth+1) 을 실시한다. depth는 알파벳을 한 개 더 방문한 상태이므로 1을 더한 값을 넣는다. 

 

이렇게 재귀함수를 반복해서 실행하다가 이미 방문한 알파벳을 만나게 되어 함수를 종료할 경우, 현재 방문하고 있는 알파벳으로부터 빠져나와서 이전 단계에서부터 다시 재귀함수를 실시해야 한다. 따라서 현재 방문하고 있는 알파벳의 visited를 False로 바꾼다. 

 

예를 들어 알파벳 보드에서 I => F => H => E 까지 말이 이동했다고 해보자. 

 

마지막에 방문한 E에서 방문할 수 있는 칸은 F밖에 없는데 이미 F는 이전에 방문한 알파벳이므로 더 이상 방문할 수 있는 칸이 없다. 따라서 말은 E를 방문하기 이전 칸인 H로 돌아와서 E가 아닌 다른 칸을 방문해야 한다. 따라서 H로 돌아온다는 의미에서 현재 방문하고 있는 E의 visited를 False로 바꾸는 것이다. 그런데 H에서도 더 이상 방문할 수 있는 칸이 없다. 이미 방문한 알파벳인 F로 둘러싸여 있기 때문이다. 따라서 H의 visited를 False로 바꾸면서 이전 칸인 F로 후퇴해야 한다. 

그런데 이전 칸인 F에서도 갈 수 있는 칸이 없다. H는 이미 for문을 통해 방문했던 칸이고, 남은 아래 칸은 이미 방문한 F이기 때문이다. 따라서 첫 칸인 I까지 후퇴하면서 F의 visited를 False로 만든다. 그러면 I에서 F가 아닌 E칸으로 움직이면서 다시 최장 길이를 구하는 시도를 해야 한다. 

 

해당 문제는 이미 방문한 알파벳을 만날 경우 더 이상 전진하지 않고 이전 단계로 돌아와서 다른 칸을 방문하는 백트래킹 문제였다. 따라서 깊이우선탐색을 하면서 현재 탐색한 칸의 visited를 False로 만듦으로써 이전 단계로 돌아오는 백트래킹을 사용하였다. 다만 python으로 제출했을 때는 시간 초과가 나고, pypy3로 제출하면 통과되었다. 

 

 

♣ 참고 자료

https://edder773.tistory.com/75

[파이썬] 탐색 알고리즘 정리 - 백트래킹

https://veggie-garden.tistory.com/24

[Python] 백트래킹 (+ DFS와 차이)