[Javascript] 백준 1987 알파벳

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

1987번: 알파벳

 

전형적인 DFS 문제이다.

조금 응용된 부분은 DFS 함수 인자에 지금까지의 알파벳을 set에 담아서 넘겨준다는 점이 있다.

let input = require('fs').readFileSync(__dirname+'/example.txt').toString().trim().split('\n');
let count = 0;

const [N, M] = input[count++].split(' ').map(Number);
const dy = [ -1, 1,  0, 0 ];
const dx = [  0, 0, -1, 1 ]
let graph = [];
let answer = -Infinity;

for(let i=0; i<N; i++){			// 입력값 2차원 배열로 만들기
    graph.push(input[count++].split(''));
}

const DFS = (y, x, crnt_set) => {
    
    if(crnt_set.size > answer){
        answer = crnt_set.size;
    }
    for(let i=0; i<4; i++){
        const next_y = y + dy[i];
        const next_x = x + dx[i];   

        if(next_y >= 0 && next_y < N && next_x >= 0 && next_x < M){
            if(!crnt_set.has(graph[next_y][next_x])){   // set에 없는 알파벳일 경우
                crnt_set.add(graph[next_y][next_x])
                DFS(next_y, next_x, crnt_set);
                crnt_set.delete(graph[next_y][next_x])
            }
        }
    }
}

DFS(0, 0, new Set(graph[0][0]));
console.log(answer);

 

시행착오를 겪은 부분이 있는데

        if(next_y >= 0 && next_y < N && next_x >= 0 && next_x < M){
            if(!crnt_set.has(graph[next_y][next_x])){   // set에 없는 알파벳일 경우
                crnt_set.add(graph[next_y][next_x])
                DFS(next_y, next_x, crnt_set);
                crnt_set.delete(graph[next_y][next_x])
            }
        }

위의 코드 부분을

 

if(next_y >= 0 && next_y < N && next_x >= 0 && next_x < M){
            if(!crnt_set.has(graph[next_y][next_x])){   // set에 없는 알파벳일 경우
                DFS(next_y, next_x, crnt_set.add(graph[next_y][next_x]));
            }
        }

이와 같이 했는데, 다른 방향으로 흘러갔다. 

나중에 같은 실수하지 않도록 기억하자.