백준 2210 JS 풀이

구하는 값

6개 숫자를 썼을 때 만들 수 있는 수

핵심 아이디어

상하좌위 DFS돌며 dep가 6일때 정지,
000111도 가능하도록 string로 합치기

구현방법

1. 인접리스트 만들고 : graph
2. 숫자담을 배열 만들고 : arr
3. 현재상태 str만들고 : cur
4. 이중포문으로 각위치마다 dfs(백트레킹)
5. dfs에서 상하좌우 탐색(백트레킹)하며 cur에 하나씩 추가, dep가 6되면 arr에 추가
6. arr를 set으로 중복 제거

코드

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

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

// console.log(graph);

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

let arr = [];
let cur = "";
function dfs(y, x, dep) {
    if (dep === 6) {
        // console.log("cur저장", cur);
        arr.push(cur);

        return;
    }

    // console.log("cur", cur);

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

        if (ny < 0 || ny >= 5 || nx < 0 || nx >= 5) continue;


        cur += graph[ny][nx];
        // console.log("cur1", cur);
        dfs(ny, nx, dep + 1);
        cur = cur.slice(0, cur.length - 1);
        // console.log("cur2", cur);
    }
}

for (let i = 0; i < 5; i++) {
    for (let j = 0; j < 5; j++) {
        cur += graph[i][j];
        dfs(i, j, 1);
        cur = cur.slice(0, cur.length - 1);
    }
}

console.log([...new Set(arr)].length);