[백준] 1987 알파벳 - javascript

📌 문제

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

📌 풀이

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

let [R, C] = input[0].split(" ").map(Number);
let board = new Array(R);
for (let i = 0; i < board.length; i++) {
  board[i] = input[i + 1].trim().split("");
}
let visit = new Array(26).fill(false); 
let ans = 0;
let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];

function DFS(x, y, cnt) {
  ans = Math.max(ans, cnt);
  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i];
    let ny = y + dy[i];
    if (nx >= 0 && ny >= 0 && nx < R && ny < C) {
      if (visit[board[nx][ny].charCodeAt() - 65] === false) {
        visit[board[nx][ny].charCodeAt() - 65] = true;
        DFS(nx, ny, cnt + 1);
        visit[board[nx][ny].charCodeAt() - 65] = false;
      }
    }
  }
}
visit[board[0][0].charCodeAt() - 65] = true;
DFS(0, 0, 1);
console.log(ans);

✔ 알고리즘 : DFS, 백트래킹

let visit = new Array(26).fill(false); 

✔ 같은 알파벳은 다시 방문하면 안되므로 좌표로 visit 배열을 설정하지 않고 알파벳의 개수대로 visit 배열을 설정하였다.

✔ 첫번째 칸인 board[0][0]에서 시작해야하므로 방문 처리를 하고 DFS탐색을 해야한다.

✔ DFS함수에서 현재 board범위 내이고 방문하지 않은 알파벳이라면 방문처리를 해주고 cnt를 1증가 시키고 DFS탐색을 이어간다. DFS 탐색이 끝나면 다시 방문처리를 해제한다.

❗ c++처럼 알파벳 방문처리를

visit[board[nx][ny] - "A"] === false

로 구현하여 체크하였더니 방문처리가 되지 않았다.

 visit[board[nx][ny].charCodeAt() - 65]

javascript에서는 charCodeAt함수를 통해 아스키코드로 변환해야하는 것 같다.

✔ 난이도 : 백준 기준 골드4