백트래킹 알고리즘은 무엇인가?
백트래킹 알고리즘은, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하하는 dfs를 기반으로 지금 경로가 맞지 않으면 경로를 더이상 가지 않고 되돌아가는 알고리즘이다.
예를 들어, 오목을 두는 상황이라고 가정하자. 그렇다면, 우리가 특정 수를 놓았을때 상대방은 어떤 수를 두고, 또 나는 그에 대응하여 어떤 수를 두는 상태들이 나타나게 되는데 이러한 것들이 백트래킹 알고리즘이다.
백준 N과 M (1) 문제로 백트래킹 이해하기.
(ref: https://www.acmicpc.net/problem/15649)
백준 N과 M 문제는 백트래킹을 기반으로 풀 수 있는 문제이다. 우리가 여기서 하고자 하는 것은 4까지의 2자리 수열을 출력하는 것이다. 이를 어떻게 접근할 수 있을까?
일단, 코드를 먼저 살펴보자.
const N = 4;
const M = 2;
const result = [];
const visited = {};
const output = [];
// 1, 2, 3 이 출력되어야 한다.
const dfs = (cnt) => {
if (cnt === M) return result.push(Array.from(output));
for (let i = 1; i <= N; i++) {
if (visited[i]) continue;
visited[i] = true;
output.push(i);
dfs(cnt + 1);
output.pop();
visited[i] = false;
}
};
dfs(0);
console.log(result);
// 1,2 , 1,3, 1,4 ...사실, 코드를 보아서도 백트래킹이 잘 이해가 가지 않았다.
하나하나씩 살펴보자.
dfs(0)이 실행되면 어떤 과정이 일어날까?
dfs(0) 이 실행되면, return 조건을 충족하지 못하므로 for - 반복문으로 진입한다.
for 반복문에서는 다음의 동작이 실행된다.
- for 반복문에서 1을 만날때 다음이 실행된다.
visited[1] = true;
output = [ 1 ] 위가 먼저 정해진 다음, dfs(1)이 실행된다.
- dfs(1) 또한 조건을 충족하지 못하므로, for문으로 진입한다.
진입하기 전 상태는 다음과 같다. (위에 나와있는 visited, output은 전역이므로 가지고 간다.)
visited[1] = true;
output = [ 1 ] for문으로 진입했는데, 1의 경우는 visited[1] === true 이므로 넘어간다.
그리고, for문의 2가 실행된다. (visited[2]가 false이므로)
visited[1] = true;
visited[2] = true;
output = [1, 2]이제 위와 같은 상태가 되었다. 그리고 dfs(2)가 실행된다.
- dfs(2)가 실행되어도 조건을 충족하지 못하므로, for문으로 진입한다.
진입하기 전 상태는 바로 위와 같다. 진입하고,1, 2는visited가true이므로 넘어가고 3을 만나 동작한다.
visited[1] = true;
visited[2] = true;
visited[3] = true;
output = [1, 2, 3];그리고 dfs(3)이 실행된다.
- dfs(3)이 실행되면, 조건이 맞으므로 현재 상태는 다음과 같다.
result = [[1, 2, 3]]
// output이 push되었다.
visited[1] = true;
visited[2] = true;
visited[3] = true;
output = [1, 2, 3];dfs(3)은 여기서 끝났다. 그런데, 콜스택에 아직 진행되지 못한 함수부분이 남아있다.
콜스택은 stack이므로 dfs(2)의 남은 부분이 먼저 호출된다.
- dfs(2)는 for문의 3의 dfs(3)을 호출하는 부분까지 동작하였고, 남은 부분이 동작한다.
(남은 부분은,output.pop(); visited[i] = false;부분이다.)
이 부분이 동작하면, 상태는 다음과 같이 바뀐다.
visited[1] = true;
visited[2] = true;
visited[3] = false;
output = [1, 2];
// 3은 false가 되고, output에서 마지막 자리가 빠진다.- dfs(2)의 for문의 4가 실행된다.
visited[1] = true;
visited[2] = true;
visited[3] = false;
visited[4] = true;
output = [1, 2, 4];그리고, dfs(3)을 만나 dfs(3)이 실행되고 조건에 맞으므로 result에 [1, 2, 4]가 들어간다.
dfs(3)은 바로 리턴되고 후입선출이므로 가장 늦게 남아있던 dfs(2)의 아랫부분이 실행된다.
dfs(2)가 마무리된 상황(for문의 4까지 돈 상황)은 다음과 같다.
visited[1] = true;
visited[2] = true;
visited[3] = false;
visited[4] = false
output = [1, 2];- dfs(1)의 for문이 이어서 실행된다.
이제, dfs(2)는 끝났고 아직 콜스택에 남아있는 dfs(1)의 for문이 이어서 실행된다. 현재는 dfs(1)의 for문의2에서 dfs(2)를 호출하는 부분이 끝났다. 그리고 그 아랫부분이 이어진다.
visited[1] = true;
visited[2] = false;
visited[3] = false;
visited[4] = false
output = [1];그리고, for문 중 3이 실행된다.
3은 현재 상태에서 false이므로 지나치지 않고 실행될 것이다.
visited[1] = true;
visited[2] = false;
visited[3] = true;
visited[4] = false
output = [1, 3];이 상태에서 dfs(2)가 실행된다.
- dfs(2)의 새로운 반복문이 1부터 실행된다.
1은, visited가 true이므로 넘어가지만 2는 실행될 것이다. 2가 실행되면 다음과 같다.
visited[1] = true;
visited[2] = true;
visited[3] = true;
visited[4] = false
output = [1, 3, 2];그리고 중간에 dfs(3)이 실행되는데, 조건에 맞으므로 result에 [1, 3, 2]가 들어간다.
그리고, dfs(2)의 2가 이어 실행된다.
visited[1] = true;
visited[2] = false;
visited[3] = true;
visited[4] = false
output = [1, 3];- 아직 dfs(2)의 for문의 3과 4가 남았다.
3은 true이므로 넘어가고, 4는 실행되며 4는 조건에 맞으므로result에 들어간다.
... 이러한 방식이 계속해서 진행된다.
코드를 하나하나씩 적어보고 그려가면서 이해하려고 하니 이해가 조금 잘 되었다.
