[node.js,백준]1987 - 알파벳

목차

 

 

 문제

링크

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

문제

세로 𝑅$R$칸, 가로 𝐶$C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1$1$행 1$1$열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 𝑅$R$과 𝐶$C$가 빈칸을 사이에 두고 주어진다. (1≤𝑅,𝐶≤20$1 ≤ R,C ≤ 20$) 둘째 줄부터 𝑅$R$개의 줄에 걸쳐서 보드에 적혀 있는 𝐶$C$개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

주저리

dfs로 푸는 문제이며 시간이 매우 빡빡했다.

이전에 하던방식이있어서 똑같이 넣었는데 그부분이 시간초과를 일어내는줄도모르고 삽질을 엄청했다..

 

말은 상하좌우로 이동할수있고 알파벳 대문자는 26개가있기때문에 방문배열은 알파벳으로 이용해주면된다.

 

가야하는 부분에 알파벳이 방문한적이없다면 재귀로 계속 반복해주면 된다.

시간 초과를 일어냈던 코드

여기에서 node를 string 으로 만들고 node.split(”_”).map(Number)이런식으로 해결했던 문제들이 많았는데 해당문제에선 이것을 했을 경우 너무 많은 호출로인해 문제를 일으켰던 것으로 보인다.. 앞으로 더 최적화를 하는방법에대해서 고민해야함을 깨달았다.

 

function go(index, node) {
    let maxCnt = index;
    let [left, right] = node.split("_").map(Number);
    let word = maze[left][right];

    alphaCheckArrays[findAlphabetPosition(word)] = true;
    for (let i = 0; i < 4; i++) {
        let x = right + dx[i];
        let y = left + dy[i];
        if (x >= 0 && x < C && y >= 0 && y < R && !alphaCheckArrays[findAlphabetPosition(maze[y][x])]) {
            maxCnt = Math.max(go(index + 1, `${y}_${x}`), maxCnt)
        }
    }
    alphaCheckArrays[findAlphabetPosition(word)] = false;

    return maxCnt;
}

풀이

 알파벳 체크 배열 초기화

• 알파벳 체크 배열은 A부터 Z까지의 알파벳이 방문되었는지 여부를 저장하는데 사용됩니다. findAlphabetPosition 함수는 알파벳을 인덱스로 변환합니다.

 방향 배열 설정

• 4개의 방향(상하좌우)으로 이동하기 위한 배열을 설정합니다.

 

 DFS함수 정의

• go 함수는 DFS를 사용하여 최대 방문 가능한 칸 수를 계산합니다. 현재 위치에서 상하좌우로 이동할 수 있는 모든 경우를 탐색하며, 방문 가능한 최대 칸 수를 갱신합니다.

 

 메인 함수 실행

• solution 함수는 DFS를 시작하는 함수입니다. 시작 위치는 (0, 0)에서 시작하며, 결과를 콘솔에 출력합니다.

 코드

 

// 알파벳
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString();


let real = input.trim().split("\n");
let [first, ...rests] = real;
let [R, C] = first.trim().split(" ").map(Number);
let maze = rests.map(row => [...row]);
let alphaCheckArrays = Array.from({ length: 26 + 1 }).fill(false);
function findAlphabetPosition(alphabet) {
    // 대문자로 변환 후 아스키 코드 값을 이용하여 위치 계산
    const position = alphabet.charCodeAt() - 65;
    return position
}
let dx = [1, -1, 0, 0];
let dy = [0, 0, -1, 1];
function go(index, x, y) {
    let maxCnt = index;
    let word = maze[y][x];

    alphaCheckArrays[findAlphabetPosition(word)] = true;
    for (let i = 0; i < 4; i++) {
        let newX = x + dx[i];
        let newY = y + dy[i];
        if (newX >= 0 && newX < C && newY >= 0 && newY < R && !alphaCheckArrays[findAlphabetPosition(maze[newY][newX])]) {
            maxCnt = Math.max(go(index + 1, newX, newY), maxCnt)
        }
    }
    alphaCheckArrays[findAlphabetPosition(word)] = false;

    return maxCnt;
}

async function solution() {

    console.log(go(1, 0, 0));
    // console.log(maxes)

}
solution();