[백준 알고리즘] 1987번 알파벳 node.js JavaScript JS

1987번: 알파벳

😉문제 풀이 설명

문제는 DFS를 사용하여 풀 수 있습니다.

---

🤨문제 풀이 실패 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")

const [R, C] = input.shift().split(" ").map(Number);
const map = input.map((v) => v.split(""));

const next = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0]
];
const visited = Array(26).fill(false);

let answer = 1;
visited[map[0][0].charCodeAt() - 65] = true;
const stack = [{ a: 0, b: 0, visited2: [...visited], count: 1 }];

while (stack.length > 0) {
  const { a, b, visited2, count } = stack.pop();
  if (count > answer) answer = count;
  for (let [a2, b2] of next) {
    if (a + a2 >= 0 && a + a2 < R && b + b2 >= 0 && b + b2 < C) {
      if (!visited2[map[a + a2][b + b2].charCodeAt() - 65]) {
        const visited2_copy = [...visited2];
        visited2_copy[map[a + a2][b + b2].charCodeAt() - 65] = true;
        stack.push({
          a: a + a2,
          b: b + b2,
          visited2: visited2_copy,
          count: count + 1
        });
      }
    }
  }
}

console.log(answer);

visited 배열을 stack에 함께 넣음으로서, 각각의 지점에서 방문했던 모든 지점을 기억하려 하였습니다.

하지만 위의 코드는 시간 초과의 결과가 나옵니다.

구글링을 통해 좀 더 효율적으로 코드를 짜는 방법을 알아봤습니다.

---

😎문제 풀이 해결 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")

const [R, C] = input.shift().split(" ").map(Number);
const map = input.map((v) => v.split(""));

const next = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0]
];
const visited = Array(26).fill(false);

let answer = 1;
visited[map[0][0].charCodeAt() - 65] = true;

function dfs({ a, b, count }) {
  if (count > answer) answer = count;
  for (let [a2, b2] of next) {
    if (a + a2 >= 0 && a + a2 < R && b + b2 >= 0 && b + b2 < C) {
      const str_index = map[a + a2][b + b2].charCodeAt() - 65;
      if (!visited[str_index]) {
        visited[str_index] = true;
        dfs({
          a: a + a2,
          b: b + b2,
          count: count + 1
        });
        visited[str_index] = false;
      }
    }
  }
}
dfs({ a: 0, b: 0, count: 1 });

console.log(answer);

실패 코드와의 차이점은 각 지점에 방문한 기록을 넣지 않았다는 것입니다.이는 재귀를 통한 단계적 수행 덕분에 가능한 것이라 생각됩니다.