1987 알파벳 (자바스크립트)

문제

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

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

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

입력

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

출력

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

====

 

문제 분석

0,0 에서부터 출발하여 모든 경로를 탐색할 것이지만 이미 한 번 나온 알파벳은 포함되지 않게 해야한다.

1. 알파벳은 총 26개니까 visit를 Set로 선언해서 방문 체크

2. DFS로 깊이 탐색을 하는게 효율적

오답노트

1. 처음에는 큐에 (0,0) 좌표와 지금까지 수집한 알파벳들을 기록하기 위한 alphabetObject를 넣어줬다.

이럴 경우 무진장 큰 그래프에서 모든 경로가 모든 알파벳을 수집할 수 있을 경우 여러 경로를 탐색하게 되면서인지 시간 초과가 발생했다. => 2% 시간초과

2. 알파벳들의 위치를 모두 기록해두는 alphabetLocations 를 선언하여 key에는 알파벳을 두고 value로는 알파벳이 위치한 좌표들을 담아주었다. 

그 뒤 0,0에서 DFS로 방문하면서 한 번 방문하게 되는 알파벳은 그 알파벳이 위치한 모든 좌표들에 visited = true를 줘서 탐색 시 종료를 유도하였다.=> 8% 시간 초과

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

const main = (input) => {
    const [n, m] = input[0].split(' ').map((v) => +v);
    const gr = [];
    for (let i = 1; i < input.length; i++) {
        gr.push(input[i].split(''));
    }

    const alphabets = {};
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            alphabets[gr[i][j]] = [...(alphabets[gr[i][j]] || []), [i, j]];
        }
    }
    const visited = new Set();
    let answer = 1;

    const dfs = (cx, cy, count) => {
        for (let i = 0; i < 4; i++) {
            const nx = cx + dx[i];
            const ny = cy + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            const currentAlphabet = gr[nx][ny];
            if (visited.has(currentAlphabet)) continue;
            visited.add(currentAlphabet);
            dfs(nx, ny, count + 1);
            visited.delete(currentAlphabet);
        }
        answer = Math.max(answer, count);
    };

    const currentAlphabet = gr[0][0];
    visited.add(currentAlphabet);
    dfs(0, 0, 1);
    console.log(answer);
};

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

main(input);