[BOJ/JavaScript] 1987: 알파벳

문제

세로 R칸, 가로 C칸의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나 적혀 있고, 좌측 상단 칸에 말이 놓여져 있다.

말은 상하좌우 인접한 네 칸 중 한 칸으로 이동할 수 있으나, 새로 이동한 칸에 적힌 알파벳은 이전에 밟지 않은 알파벳이어야만 한다.

좌측 상단에서 시작하여 말이 최대로 지날 수 있는 칸의 개수를 구하라.

• 1 ≤ R, C ≤ 20

풀이

주어진 시간 제한이 2초, R, C의 범위가 1~20인 것에서 백트래킹으로 풀 수 있을 정도의 입력 데이터가 주어진다는 것을 확인할 수 있었다.

 

말은 현재 위치한 칸에서 갈 수 있는 곳을 택하고 탐색해 최장 거리를 매 재귀마다 최장 거리를 계산해준다.

핵심은 '이전 상태를 어떻게 저장할 것인가'에서 나뉘게 된다. 깊은 고민없이 접근했다가 많은 시간 초과를 마주칠 수 밖에 없었다. 문제의 정답 비율이 28% 정도로 낮은 이유는 바로 이 때문이 아닐까 싶다.

 

처음 시도한 방법은 Set을 활용한 것이었다. 탐색이 진행될 때마다 Set에서 다음 알파벳이 존재하는지 검사(`has`)하고 새로운 Set을 할당하여 다음 재귀에 전달해주었는데, 이 부분에서 오버헤드가 컸는지 시간 초과가 발생했다.

 

다음은 문자열로 저장했다. 이번엔 `includes` 메서드로 알파벳의 방문 여부를 저장했는데 정답을 향해 가는가 싶더니 중간을 조금 넘겨 역시 오버헤드가 컸는지 시간 초과를 일으켰다.

 

GPT에게 조언을 구하니 비트마스킹을 활용해보라고 했다. 비트마스킹을 활용해 방문 여부를 체크하니 다른 정답들에 비해서도 아주 효율적이었다. 아직 비트마스킹 활용법에 익숙하지 않은데, 곳곳에 유용하게 사용되니 확실히 익혀둬야 겠다.

1 << a // a번째 위치의 비트를 켬
bit & (1 << a) === 0 // a번째 비트가 켜져 있음
bit | (1 << a) // bit의 a번째 비트를 켬
bit & ~(1 << a) // a번째 비트를 끔
bit ^ (1 << a) // a번째 비트를 토글

 

다른 정답 코드들을 보니 백트래킹으로도 가능하다는 것을 알게 되었다. 비트마스킹과 비교했을 때의 성능도 비슷하다. 

 

💡 BFS로도 풀 수 있지 않을까 생각했지만 이 문제는 BFS로 풀기엔 너무 비효율적이었다. 그 이유가 뭘까?

1. BFS로 구현하려면 중간 상태를 큐에 모두 저장해야 한다. 최장 거리 문제는 경로가 길어질 수록 조합이 많아지고, 이는 상태 공간이 가파르게 증가한다는 것을 의미한다. 매 경로마다 방문한 알파벳이 다르면 다른 상태이므로, 모든 조합을 전부 큐에 넣어두고 연산하면 너무 많은 메모리를 사용한다.
2. "가지치기"가 사실상 불가능하다.  DFS는 현재 경로에서 더 나아갈 수 없다면 바로 멈출 수 있지만, BFS는 큐에 쌓은 모든 경로를 다 꺼내봐야 한다.

 

코드

Ver 1. 비트마스킹을 활용한 DFS

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

const [R, C] = input[0].split(" ").map(Number);
const board = input.slice(1).map(e => e.split(""));
const dx = [1, -1, 0, 0];
const dy = [0, 0, -1, 1];
let max = 0;

function dfs(r, c, visited, count) {
    max = Math.max(max, count);

    for (let i = 0; i < 4; i++) {
        const nr = r + dx[i];
        const nc = c + dy[i];
        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;

        const ch = board[nr][nc].charCodeAt(0) - 65;
        if ((visited & (1 << ch) === 0)) {
            dfs(nr, nc, visited | (1 << ch), count + 1);
        }
    }

}

dfs(0, 0, 1 << (board[0][0].charCodeAt(0) - 65), 1);

console.log(max);

 

Ver 2. 방문 배열을 활용한 백트래킹

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

const [R, C] = input[0].split(" ").map(Number);
const board = input.slice(1).map(e => e.split(""));

const visited = Array(26).fill(false);
const dx = [1, -1, 0, 0];
const dy = [0, 0, -1, 1];
let max = 0;

function charToNumber(ch) {
    return ch.charCodeAt(0) - 65;
}

function dfs(r, c, count) {
    max = Math.max(max, count);

    for (let i = 0; i < 4; i++) {
        const nr = r + dx[i];
        const nc = c + dy[i];
        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;

        const ch = charToNumber(board[nr][nc]);
        if (!visited[ch]) {
            visited[ch] = true;
            dfs(nr, nc, count + 1);
            visited[ch] = false;
        }
    }
}

visited[charToNumber(board[0][0])] = true;
dfs(0, 0, 1);

console.log(max);