[JS] 백준 1978 : 알파벳 - 그래프, 이론그래프, 탐색, 깊이 우선 탐색,백트래킹

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

1987번: 알파벳

 

풀이방법

1.DFS로 상하좌우를 탐색한다.

2. 탐색하면서 지나온 알파벳은 배열에 저장한다.

3. 다음 알파벳을 검사할 때 저장해놓았던 배열을 indexOf로 검사한다

4. -1이 나오면 겹치는 알파벳이 없는 것이므로 진행해준다.

5. 이때 visited라는 2차원 배열로 방문표시를 해줘야 무한재귀가 걸리지않는다.

6. 또한 DFS로 뻗어나갈 때 상하 좌우 모든 경우로 뻗어나가야하므로 저장했던 알파벳을 다시빼주고, 방문표시도 제외해서 다음 반복을 준비한다( 즉 오른쪽으로 검사했다면 다음은 왼쪽 아래쪽 위쪽도 뻗어가면서 최대 경로를 찾아야한다.)

 

 

내 제출

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

let [R,C]=input.shift().split(" ").map(Number);
let arr = [];
for (var i = 0; i < R; i++){
    arr.push(input.shift().split(""));
}

let remember = [];

let dx = [1, 0, 0, -1];
let dy = [0, 1, -1, 0];
let visited = Array.from({length: R},()=>Array(C).fill(0))

let max = 0;

function DFS(L, y, x) {
    for (var i = 0; i < 4; i++){
        let nx = x + dx[i];
        let ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < C && ny < R && visited[ny][nx] == 0) {
            if (remember.indexOf(arr[ny][nx]) == -1) {
                remember.push(arr[ny][nx]);
                visited[ny][nx] = 1;
                DFS(L + 1, ny, nx);
                remember.pop();
                visited[ny][nx] = 0;
            }
        }
    }
    max=Math.max(max,L)
}
visited[0][0] = 1;
remember.push(arr[0][0]);
DFS(1, 0, 0);

console.log(max)

 

💢어려웠던 점

1. DFS를 진행할 때 처음에 오른쪽으로 진행한뒤 다시 되돌아오는 것을 안해줘서 최대 경로가 나오지 않았다.

- 상하좌우 4개의 경우 중 오른쪽으로 뻗어나가고 만약 그길이 아니면  다시 되돌아와서 다른 길로 가야하는데 그것을 위해 저장했던 알파벳을 빼주고 방문표시도 다시 제외해줘야한다.

...

if (remember.indexOf(arr[ny][nx]) == -1) {
    remember.push(arr[ny][nx]);
    visited[ny][nx] = 1;
    DFS(L + 1, ny, nx);
    remember.pop();
    visited[ny][nx] = 0;
}


...