[백준 1987 - Node.js] 알파벳

 

🔗 문제 링크

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

1987번: 알파벳

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split("\n");
const [R, C] = input[0].split(' ').map(v => +v);
const board = input.slice(1).map((v) => v.split(""));
const offsetX = [0, 0, -1, 1];
const offsetY = [-1, 1, 0, 0];

const dfs = (x, y, count, visited) => {
  let maxCount = count;

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

  return maxCount;
};

const visited = Array(26).fill(false);
console.log(dfs(0, 0, 1, visited));

시작점에서부터 DFS를 하면서 지금까지 A부터 Z까지 알파벳의 방문 여부를 기록하면서 가장 멀리 간 경우의 칸 수를 구하여 해결할 수 있다.

 

어떤 알파벳이 나올지는 모르지만 반드시 대문자 알파벳만 나오기 때문에 A~Z까지의 26개 알파벳의 방문 여부를 visited에 초기화한다. 그리고 DFS를 하면서 방문 여부를 따질 때 board[x][y]의 UTF-16 코드를 활용하여 A부터 Z까지 알파벳을 0 ~ 25에 대응시켰다.

 

먼저 현재 방문한 알파벳의 방문 여부를 true로 바꾼다. 그 다음, 상하좌우 4방향에 대하여 재귀적으로 DFS를 실행하여 더 멀리 갈 수 있는 경우를 찾아내고, 4방향에 대한 탐색이 끝나면 직전에 방문한 알파벳의 방문 여부를 false로 되돌려 놓는다(visited는 참조값이기 때문에 계속 같은 배열을 가리키고 있기 때문). 마지막으로 4방향에 대한 탐색의 결과로 가장 멀리 간 경우의 칸 수를 반환한다.

 

모든 갈 수 있는 경로를 탐색한 후에 재귀호출이 종료되면 최종적으로 가장 멀리 간 경로의 칸 수를 반환하게 된다.

 

 

💡 새로 알게 된 점

이번 문제를 풀면서 DFS 문제를 풀 때, 그리고 자바스크립트로 문제를 풀 때 주의해야 할 점들을 몇 가지 알게 되었다.

 

1. 재귀호출의 횟수를 최대한 줄여라.

if (nx >= 0 && nx < R && ny >= 0 && ny < C && !visited[board[nx][ny].charCodeAt() - 65]) {
  maxCount = Math.max(maxCount, dfs(nx, ny, count + 1, visited));
}

처음에 이 문제를 풀 때 상하좌우 4방향을 탐색하는 조건문에서 상하좌우의 칸에 이미 방문했던 알파벳이 있는지 확인하는 !visited[board[nx][ny].charCodeAt() - 65]를 쓰지 않고, 아래처럼 dfs 함수의 처음 부분에서 확인하는 방식으로 코드를 짰었다. 

const dfs = (x, y, count, visited) => {
  if (visited[board[x][y].charCodeAt() - 65]) {
    return count;
  }

  let maxCount = count;

  visited[board[x][y].charCodeAt() - 65] = true;
  offsetX.forEach((dx, i) => {
    const nx = x + dx;
    const ny = y + offsetY[i];
    if (board[nx]?.[ny]) {
      maxCount = Math.max(maxCount, dfs(nx, ny, count + 1, visited));
    }
  });
  visited[board[x][y].charCodeAt() - 65] = false;

  return maxCount;
};

위 코드는 시간 초과가 난다. 재귀 호출 횟수가 불필요하게 많기 때문이다.

조건문의 위치를 옮겨서 겨우 통과할 수 있엇다.

 

2. forEach보다는 그냥 for문을 사용하자

상하좌우 4방향 탐색 코드를 forEach에서 for문으로 변경하고 시간이 2배 단축되었다.

사실 원래 for문 쓰는 것이 더 빠르다는 것을 알고 있었지만, 문제 통과 여부에는 큰 영향이 없을 것이라 생각했었다.

효율성을 따지는 문제에서는 이러한 부분도 영향이 크게 미칠 수 있을 것 같다.

 

3. 방향을 탐색할 때 정직하게 좌표를 검사하자(옵셔널 체이닝 연산자 쓰지 말자)

1번에서 시간 초과가 났었다던 코드를 보면 상하좌우의 좌표 (nx, ny)의 유효성 검사를 일일이 하지 않고 board[nx]?.[ny] 하나로 처리한 것을 볼 수 있다. undefined 또는 null의 프로퍼티를 참조하려고 할 때 에러가 발생하는데, 자바스크립트의 옵셔널 체이닝 연산자(?.)를 사용하면 undefined / null 일 경우에 참조를 하지 않고 즉시 undefined를 반환한다.

 

나는 코드의 길이가 긴 것이 싫어서 옵셔널 체이닝 연산자를 사용한 꼼수를 썼다. 그러나 그냥 정직하게 일일이 nx, ny의 범위를 0 <= nx && nx < R && 0 <= ny && ny < C로 검사하니까 시간이 또 두 배 단축되었다.