이번 글에서 다룰 문제는 백트래킹(Backtracking) 기법을 활용하는 대표적인 그리드 탐색 문제입니다. 2차원 격자(grid)에는 다음과 같은 네 가지 종류의 칸이 존재합니다.
- 1 : 시작 칸(starting square) — 격자에 정확히 하나만 존재합니다.
- 2 : 도착 칸(ending square) — 마찬가지로 정확히 하나만 존재합니다.
- 0 : 지나갈 수 있는 빈 칸(empty square)
- -1 : 지나갈 수 없는 장애물(obstacle)
우리가 작성해야 할 함수는 시작 칸에서 도착 칸까지 이동하면서, 장애물이 아닌 모든 칸을 정확히 한 번씩만 지나가는 상하좌우 4방향 경로의 개수를 반환해야 합니다.
예제 코드
const arr = [
[1,0,0,0],
[0,0,0,0],
[0,0,2,-1]
];
const uniquePaths = (arr, count = 0) => {
const dy = [1,-1,0,0], dx = [0,0,1,-1];
const m = arr.length, n = arr[0].length;
const totalZeroes = arr.map(row => row.filter(num => num ===
0).length).reduce((totalZeroes,nextRowZeroes) => totalZeroes +
nextRowZeroes, 0);
const depthFirstSearch = (i, j, covered) => {
if (arr[i][j] === 2){
if (covered === totalZeroes + 1) count++;
return;
};
for (let k = 0; k < 4; k++)
if (i+dy[k] >= 0 && i+dy[k] < m && j+dx[k] >= 0 && j+dx[k] < n
&& arr[i+dy[k]][j+dx[k]] !== -1 ){
arr[i][j] = -1;
depthFirstSearch(i+dy[k],j+dx[k],covered+1);
arr[i][j] = 0;
}
return;
};
for (let row = 0; row < m; row++)
for (let col = 0; col < n; col++)
if (arr[row][col] === 1){
arr[row][col] = -1;
depthFirstSearch(row,col,0);
break;
}
return count;
};
console.log(uniquePaths(arr));코드 설명
- 방향 배열과 빈 칸 개수 계산: 격자를 순회할 때 상하좌우 네 방향으로 이동할 수 있도록
dy,dx방향 배열을 준비하고, 재귀의 종료 조건(base case)에 도달했을 때 모든 칸을 지나왔는지 검사할 수 있도록 행렬 내 빈 칸(0)의 총 개수를 미리 세어 둡니다. - DFS 백트래킹 함수 구성: 깊이 우선 탐색(DFS) 기반의 백트래킹 함수를 만들어, 현재 진행 중인 경로 위의 칸을
-1로 표시하여 같은 칸을 다시 방문하지 않도록 합니다. 그리고 도착 칸(2)에 도달한 시점에 지나온 칸 수가 전체 빈 칸 수와 일치하는지 확인하여 유효한 경로인지 판별합니다. 탐색이 끝나면 칸을 다시0으로 되돌려 다른 경로 탐색이 가능하게 하는 것이 백트래킹의 핵심입니다. - 탐색 시작 및 결과 반환: 마지막으로 시작 칸(1)을 찾아 해당 위치에서 DFS를 실행하고, 조건을 만족하는 모든 완전한 경로의 개수를 세어 반환합니다.
실행 결과
위 코드를 콘솔에서 실행하면 다음과 같은 결과가 출력됩니다.
2
즉, 주어진 격자에서 시작 칸부터 도착 칸까지 모든 빈 칸을 정확히 한 번씩 지나가는 서로 다른 경로는 총 2개입니다. 이처럼 백트래킹은 가능한 모든 경로를 탐색하되, 조건에 맞지 않는 경로는 되돌아가서 가지치기를 하기 때문에 이런 유형의 완전 탐색 문제에 매우 적합한 패턴입니다.