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

Untitled

Untitled

Untitled

아직 방문하지 않은 정점이라도 그 정점이 이미 나왔던 알파벳이 적힌 칸이면 방문하면 안된다.

그러므로 지금까지 나온 알파벳에 대한 정보도 같이 넘겨줘야 한다.

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

let [size, ...values] = input;

let [row, col] = size.split(" ").map((v) => +v);

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
// 상, 하,좌,우

const arr = values.map((row) => row.split(""));

let maxValue = -1;

const dfs = (pointX, pointY, visit, cnt) => {
	
// pointX는 방문하려는 정점의 row 값
// pointY는 방문하려는 정점의 column 값 
// visit는 탐색하면서 방문한 알파벳 내역

  let adj = 0;

  visit[arr[pointX][pointY]] = true;
// 방문처리 => 여기서 방문처리는 해당 알파벳을 방문했음으로 표시한다. 
// 어차피 좌표가 아직 방문하지 않은 좌표여도 알파벳이 이미 나온 알파벳이면 방문하지 않아야 하기 때문에 방문의 기준을 알파벳으로 함.
// ex) visit[C] = true. C알파벳을 방문했음.

  for (let i = 0; i < 4; i++) {
    let X = pointX + dx[i];
    let Y = pointY + dy[i];
// 이웃 좌표를 구함

    if (X >= 0 && Y >= 0 && X < row && Y < col && !visit[arr[X][Y]]) {
      adj++;
      dfs(X, Y, visit, cnt + 1);
      visit[arr[X][Y]] = undefined;
				// 해당 정점을 방문하고 나서 return 했을 때 방문내역을 원래대로 돌려놔야함
    }
  }

  if (!adj && maxValue < cnt) {
// 이웃 정점이 없을 때 return 지점
    maxValue = cnt;
    return;
  }
};

const sol = () => {
  dfs(0, 0, {}, 1);
  console.log(maxValue);
};

sol();