[백준] 1987번 알파벳 Javascript(NodeJs)

문제 링크

https://www.acmicpc.net/problem/1987

알고리즘: DFS, 백트래킹

문제 요약

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열)에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 말의 이동 경로에는 중복된 알파벳이 존재하면 안된다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오.

풀이 요약

이 문제의 핵심은 알파벳을 검사할 때 O(1)로 검사해야한다. 그래서 생각한 방법은 배열을 26의 크기로 할당하고, false로 채워준다. => 알파벳이 총 26개이기 때문에
그리고 알파벳을 만났을 때 아스키코드로 변환한 값에 - 65를 해서 그 값의 인덱스를 가지는 ab_check 배열이 true인지 false인지 판별해서 false이면 아직 해당 알파벳을 지나오지 않은 것이므로 통과시키고 그다음 깊이로 이동한다. 이런 식으로 반복하다 보면 시간 초과 없이 말의 최대 이동 길이를 구할 수 있다.

소스코드

const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let [R,C] = inputData[0].trim().split(' ').map(x=>x*1);
let board = Array.from(Array(R), () => Array(C));
let visited = Array.from(Array(R), () => Array(C).fill(false));
let ab_check = new Array(26).fill(false);
let size_map = new Map();
for(let i=1; i<inputData.length; i++) {
    let input = inputData[i].trim().split('');
    for(let j=0; j<input.length; j++) {
        board[i-1][j] = input[j];
        if(!size_map.has(input[j])) {
            size_map.set(input[j],true);
        }
    }
}
let max_cout = size_map.size;
let wx = [0,0,-1,1]; 
let wy = [-1,1,0,0];
let answel = 1;
let end = false;
visited[0][0] = true;
ab_check[board[0][0].charCodeAt(0) - 65] = true;
DFS(0,0,1);
console.log(answel);

function DFS(x,y,cout) {
    if(!end) {
        if(cout === max_cout) {
            answel = cout;
            end = true;
            return;
        } else {
            for(let i=0; i<4; i++) {              
                let nx = x + wx[i];
                let ny = y + wy[i];
                if((nx>=0 && nx<=C-1) && (ny>=0 && ny<=R-1)) {
                    if(!visited[ny][nx]) {
                        let al_ind = board[ny][nx].charCodeAt(0) - 65
                        if(!ab_check[al_ind]){
                            visited[ny][nx] = true;
                            ab_check[al_ind] = true;
                            DFS(nx,ny,cout+1);
                            visited[ny][nx] = false;
                            ab_check[al_ind] = false;
                        }
                    }
                }
            }
            if(answel < cout) {
              answel = cout;
            }
        }
    }
}