[백준/JS] 컴백홈 1189

문제

문제풀이

백트래킹을 이용하는 문제입니다.

일단 백트래킹이란 완전탐색의 아이디어에서 불필요한 분기를 가지치기 하는 것 입니다.
즉, 완전탐색을 할 때 필요없는 부분은 탐색하지 않겠다는 것으로 보면 됩니다.

그러면 이런 백트래킹은 언제 적용을 해야할까요?

바로, 현재 상태를 결정하기 위한 여러 경우의 수가 존재하는 경우에 사용하면 됩니다.

백트래킹은 BFS와 DFS로 모두 구현은 가능하나 DFS 가 더 구현하기 쉽다고 합니다.

백트래킹이란?
백트래킹적용사례

결과코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './test.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');

let [R, C, K] = input.shift().split(' ').map(Number);

let arr = [];
for (let i = 0; i < R; i++) {
    arr.push(input.shift().split(''));
}

let dx = [0, 0, -1, 1];
let dy = [1, -1, 0, 0];
let ans = 0;

function dfs(x, y, cnt) {
    if (x === C - 1 && y === 0 && cnt === K) ans += 1;
    else {
        arr[y][x] = 'T';

        for (let d = 0; d < 4; d++) {
            let nx = x + dx[d];
            let ny = y + dy[d];

            if (nx < 0 || ny < 0 || nx >= C || ny >= R) continue;
            if (arr[ny][nx] === '.') {
                arr[ny][nx] = 'T';
                dfs(nx, ny, cnt + 1);
                arr[ny][nx] = '.';
            }
        }
    }
}

dfs(0, R - 1, 1);
console.log(ans);