백준 1189 JS 풀이

구하는 값

왼쪽 맨 밑에서부터 오른쪽 맨 위까지 K 번만에 가는 경우의 수

핵심 아이디어

DFS로 상하좌우를 훑으면서 범위밖 || 벽 인경우는 제끼고 방문안한곳이면 방문처리하고 DFS 탄 후 빠져나오면 방문취소, DFS탈때는 Dep를 1씩 늘려가며 Dep 가 K이면서 위치가 오른쪽 맨 위인 경우에만 cnt++

구현방법

DFS + 백트레킹

코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split("\n")

const [r, c, k] = input[0].split(" ").map(Number);

const graph = [];
for (let i = 1; i <= r; i++) graph.push(input[i].split(""));

const visited = Array.from({ length: r }, () => new Array(c).fill(false));

const dx = [-1, 1, 0, 0],
    dy = [0, 0, -1, 1];

let cnt = 0;
function dfs(y, x, dep) {
    if (dep === k) {
        if (y === 0 && x === c - 1) cnt++;

        return;
    }

    // visited[y][x] = true;

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

        if (ny < 0 || ny >= r || nx < 0 || nx >= c || graph[ny][nx] === "T") continue;

        if (!visited[ny][nx]) {
            visited[ny][nx] = true;
            dfs(ny, nx, dep + 1);
            visited[ny][nx] = false;
        }
    }
}
visited[r - 1][0] = true;
dfs(r - 1, 0, 1);

console.log(cnt);