백준 1987번 알파벳

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

문제

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

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

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

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

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

입력 예시 1

2 4
CAAB
ADCB

출력 예시 1

3

입력 예시 2

3 6
HFDFFB
AJHGDH
DGAGEH

출력 예시 2

6

입력 예시 3

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

출력 예시 3

10

---

풀이/접근 방법(JavaScript)

전형적인 DFS, 백트래킹 문제였다.

처음에는 지나간 알파벳을 배열에 집어넣고 arr.includes() 방식으로 중복 알파벳인지 확인했는데 역시나.. 시간초과가 떴다.

시간초과가 나지 않도록 알파벳 중복체크를 하려면...
알파벳이 26자인 점을 고려하여, 길이가 26인 배열을 만들고
.charCodeAt()으로 알파벳의 유니코드 값을 구해 인덱스로 활용하면 된다.
예를들어 A의 유니코드 값은 65이기 때문에, -65를 해주어 인덱스를 0으로 만들어주면 된다.

0,0 지점에서 상하좌우 4방향으로 DFS 탐색을 시작하는데,
중요한 점은 더이상 탐색이 불가하면 해당 지점에서 구할수 있는 경우의 수는 모두 확인한 것이기에, 방문했던 기록을 초기화 한 후 다른 경로로 다시 탐색해야 한다는 것이다.(백트래킹)

코드(JavaScript)

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

const [R, C] = input.shift().split(" ").map(Number);
const board = input.map((item) => item.split(""));
const alphabet = new Array(26).fill(false);
const dir = [
  [-1, 0],
  [0, 1],
  [1, 0],
  [0, -1],
];
let answer = 0;

dfs(0, 0, 1);
console.log(answer);

function dfs(i, j, cellCnt) {
  alphabet[board[i][j].charCodeAt() - 65] = true;
  answer = Math.max(answer, cellCnt);
  for (let d of dir) {
    const [dx, dy] = [i + d[0], j + d[1]];
    if (isValidRange(dx, dy) && !alphabet[board[dx][dy].charCodeAt() - 65]) {
      dfs(dx, dy, cellCnt + 1);
      alphabet[board[dx][dy].charCodeAt() - 65] = false;
    }
  }
}

function isValidRange(i, j) {
  if (i < 0 || i >= R || j < 0 || j >= C) return false;
  else return true;
}

---