[백준]1987번 '알파벳' 문제 풀이 - JavaScript

[백준]1987번 '알파벳' 문제 풀이 - JavaScript

문제

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

 

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

 

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

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20)

출력

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

예제 입력 1

3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력 1

6

👉 풀이 코드

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

const [r, c] = input[0].split(' ').map(Number);
const arr = [];
for (let i = 1; i <= r; i++) arr.push(input[i]);

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

function dfs(depth, x, y) {
  maxDepth = Math.max(maxDepth, depth);
  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];
    if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
    if (visited[arr[nx][ny].charCodeAt() - 65]) continue;
    visited[arr[nx][ny].charCodeAt() - 65] = true;
    dfs(depth + 1, nx, ny);
    visited[arr[nx][ny].charCodeAt() - 65] = false;
  }
}

visited[arr[0][0].charCodeAt() - 65] = true;
dfs(1, 0, 0);

console.log(maxDepth);

👉 풀이 해설

우리가 탐색할 수 있는 조건은 표에서 벗어나지 않는 범위와 방문하지 않았던 알파벳으로 탐색을 할 수 있다.

상하좌우로 갈 수 있는지 탐색하기 위해 먼저 dx, dy 테크닉을 활용해서 4 방향으로 갈 수 있는 좌표가 필요하다.

 

먼저, dfs 함수를 호출하기 전에 첫번째 출발점부터 시작하기 때문에 출발점을 방문처리 해주고 시작한다.

dfs 함수는 깊이와 다음 이동할 x, y 좌표가 인수로 필요하다.

현재 이동한 깊이(탐색 범위)가 이전 이동했던 깊이(탐색 범위)보다 크다면 현재 깊이의 값으로 담아준다.

dfs 함수에서는 방문이 가능한지 검사 후 방문처리를 해주면서 재귀적으로 호출 후 호출이 끝나면 방문 처리를 해제한다.

 

방문처리를 하는 과정에 있어서, ASCII코드로 방문 처리를 하고있다.

처음에 배열에 값을 push, pop 하는 형태로 했었는데, 이렇게 하면 시간초과가 되어서 정답 처리를 받지 못하였다.

그래서 대문자 알파벳에 대한 값을 넣기 때문에 ASCII코드를 index로 활용해서 방문처리를 해주었다.

대문자 알파벳의 ASCII 코드는 65 ~ 90까지이기 때문에 ASCII코드에 -65를 해줌으로써 0~25까지 배열을 통해 방문처리를 할 수 있었다.

이렇게 바로 index로 접근해서 하기 때문에 방문을 했는지 확인하기 위한 연산의 시간복잡도는 O(1)이 된다.

 

마지막으로 최대 깊이의 값을 담아두었던 maxDepth를 출력하면 정답 처리를 받을 수 있다.