[백준1987_자바스크립트(javascript)] - 알파벳

🔴 문제

알파벳

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [rc, ...map] = fs.readFileSync(path).toString().trim().split('\n');
const [r, c] = rc.split(' ').map(Number);
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
const set = new Set();
const visited = Array.from({ length: r }, () => Array(c).fill(false));
let ans = -1;

const bt = (x, y) => {
  if (ans < set.size) ans = set.size;

  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];

    if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
    if (visited[nx][ny]) continue;
    if (set.has(map[nx][ny])) continue;

    visited[nx][ny] = true;
    set.add(map[nx][ny]);
    bt(nx, ny);
    visited[nx][ny] = false;
    set.delete(map[nx][ny]);
  }
};

set.add(map[0][0]);
visited[0][0] = true;

bt(0, 0);

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

문제를 보자마자 벡트래킹이라는 생각이 들었다.
시작위치은 0,0 좌표부터 벡트래킹으로 순회하면서 다음에 갈 위치가 맵 범위 안에 있고, 미방문상태이고, 이미 내가 방문했던 알파벳이 아니라면 방문체크를 한 뒤 해당 알파벳을 set에 넣고 다음 탐색을 한다.
다만 이렇게 구현했을 경우 7초라는 어마무시한 시간이 걸린다. 실제 구현은 2초 이내지만 추가 시간를 줘서 겨우 통과된 코드

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [rc, ...map] = fs.readFileSync(path).toString().trim().split('\n');
const [r, c] = rc.split(' ').map(Number);
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
let ans = 0;
const visited = Array(26).fill(false);

const bt = (x, y, count) => {
  ans = Math.max(ans, count);

  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];

    if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;

    const charCode = map[nx][ny].charCodeAt(0) - 'A'.charCodeAt(0);
    if (!visited[charCode]) {
      visited[charCode] = true;
      bt(nx, ny, count + 1);
      visited[charCode] = false;
    }
  }
};

const startCharCode = map[0][0].charCodeAt(0) - 'A'.charCodeAt(0);
visited[startCharCode] = true;
bt(0, 0, 1);

console.log(ans);

따라서 set을 사용해 알파벳의 정보를 저장하는 것이 아니라 26의 크기를 가지는 배열과 알파벳의 아스키 코드값을 이용해 인덱스로 연산하는 것이 훨씬 빠르다.
혹은 비트마스킹을 사용해도 된다는데 비트마스킹과는 친하지 않기 때문에....

오늘 배운점 : 배열에 값을 추가/삭제하는 것보다 set과 map에 값을 추가/삭제하는 것이 빠르지만, 값을 조회할때는 일반 배열에 인덱스 연산을 하는 것이 set과 map으로 조회하는 것 보다 빠르다.

🔵 Ref