[백준] 1987 알파벳 (Javascript)

문제

BOJ1987_알파벳

풀이

요구사항

R * C 크기의 보드의 각각에 칸에 알파벳 대문자가 있고, (0,0)위치부터 출발하여 상,하,좌,우로 이동한다.
이미 방문한 적 있는 알파벳이 있는 칸으로는 이동하지 못한다.
이때 최대 몇 칸까지 방문할 수 있는지 출력하시오.

해결방안

DFS+백트래킹 (시간초과)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [R, C] = input[0].split(' ').map(Number);
const board = input.slice(1, 1 + R);
const visited = Array.from({ length: R }, () => Array(C).fill(false));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const map = new Map();
let answer = 0;

function dfs(y, x, count) {
    const alpha = board[y][x];
    answer = Math.max(answer, count);
    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < C && ny < R && !visited[ny][nx] && !map.has(board[ny][nx])) {
            visited[ny][nx] = true;
            map.set(board[ny][nx], 1);
            dfs(ny, nx, count + 1);
            map.delete(board[ny][nx]);
            visited[ny][nx] = false;
        }
    }
}

map.set(board[0][0]);
dfs(0, 0, 1);
console.log(answer);

방문한 알파벳들을 Map 자료구조에 저장한다. 그리고 상하좌우를 확인하며 다음 칸의 알파벳이 Map에 저장되어있지 않고, 방문한 적 없는 칸일 경우에만 이동한다.

하지만 위와같이 코드를 작성했더니 시간초과가 나왔다 ㅠㅠ

DFS+백트래킹 (통과)

결국 다른 코드를 참고했다.

생각해보니 다음 칸으로 이동할 때 이미 방문한 칸인지, 이미 경로에 포함되어있는 알파벳인지 확인하는 과정을 map과 visited로 나눌 필요가 없었다.

다음 칸의 알파벳이 이미 지나온 경로에 포함되어있는 알파벳이라면, 다음 칸 자체의 방문 유무를 확인할 필요 없이 다음 칸은 가면 안되는 칸이기 때문이다.

따라서 visited를 알파벳 대문자의 개수인 26칸으로 만들고, 이미 방문한 적 있는 알파벳인지만 확인하여 방문을 해주면 된다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [R, C] = input[0].split(' ').map(Number);
const board = input.slice(1, 1 + R);
const visited = Array(26).fill(false);
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
let answer = 0;

function dfs(y, x, count) {
    answer = Math.max(answer, count);
    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < C && ny < R) {
            const charCode = board[ny][nx].charCodeAt() - 65;
            if (!visited[charCode]) {
                visited[charCode] = true;
                dfs(ny, nx, count + 1);
                visited[charCode] = false;
            }
        }
    }
}

visited[board[0][0].charCodeAt() - 65] = true;
dfs(0, 0, 1);
console.log(answer);

근데 시간 초과가 났던 코드에서 Map 자료구조는 해시 알고리즘을 사용하기 때문에 has, set, delete 메서드는 거의 $O(1)$의 시간 복잡도로 데이터를 처리한다.

따라서 시간 차이는 별로 없었을 것 같는데 왜 시간초과가 나왔었는지는 잘 모르겠다.

아마 아슬아슬하게 시간초과가 나왔던 것 같다.

속도 개선

알파벳을 아스키코드로 사용할거면 일일히 아스키코드로 변환해주는 대신 board에 저장된 알파벳을 처음부터 아스키코드로 저장해주면 일일히 아스키코드로 변환해줄 필요가 없기 때문에 시간이 단축된다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [R, C] = input[0].split(' ').map(Number);
const board = input.slice(1, 1 + R).map((e) => e.split('').map((e) => e.charCodeAt() - 65));
const visited = Array(26).fill(false);
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
let answer = 0;

function dfs(y, x, count) {
    answer = Math.max(answer, count);
    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < C && ny < R && !visited[board[ny][nx]]) {
            visited[board[ny][nx]] = true;
            dfs(ny, nx, count + 1);
            visited[board[ny][nx]] = false;
        }
    }
}

visited[board[0][0]] = true;
dfs(0, 0, 1);
console.log(answer);