백준 1987번: 알파벳(javascript, DFS, 백트래킹)

말이 지날 수 있는 최대의 칸 수를 구하는 문제이다. 최대의 칸을 구해야 하기 때문에 단순 BFS가 아닌 완전탐색 혹은 백트래킹을 이용해 문제를 풀어야 하겠다고 생각했다. 왜냐하면 DFS나 BFS는 한번 방문한 곳은 다시 방문하지 않는데 이 때문에 방문경로에 따라 최대값이 달라지는 경우가 생기기 때문이다.

 

백트래킹 풀이를 위해서 방문배열을 만들었는데 아스키코드를 이용해 방문을 체크하였다. 왜냐하면 Set자료형에 방문한 알파벳을 넣을수도 있지만 Set은 원소를 집어넣을 때 O(n)이 필요하지만 아스키코드를 이용해 배열의 인덱스에 바로 접근하면 O(1)로 시간복잡도를 줄일 수 있기 때문이다.

 

그리고 DFS의 인수로 cnt를 주어서 DFS가 재귀할 때마다 cnt에 1을 더해 최대값을 구하고자 했다.

 

이를 이용해 푼 코드는 다음과 같다.

 

const fs = require('fs');
let input = fs.readFileSync("/dev/stdin").toString().trim().split('\n')

const [R, C] = input[0].split(' ').map(a=> Number(a))
let board = []
for(let i=0; i<R; i++){
    board[i] = input[i+1].split('')
}

let visited = new Array(26).fill(0)
visited[board[0][0].charCodeAt(0)-65] = 1
const dx = [0,0,1,-1]
const dy = [1,-1,0,0]

let answer = 0

function DFS(r,c,cnt){
    answer = Math.max(answer, cnt)
    for(let i=0; i<4; i++){
        const nx = r + dx[i]
        const ny = c + dy[i]
        if(0<=nx && nx < R && 0<= ny && ny< C && !(visited[board[nx][ny].charCodeAt(0)-65])){
            visited[board[nx][ny].charCodeAt(0)-65] = 1
            DFS(nx,ny,cnt+1)
            visited[board[nx][ny].charCodeAt(0)-65] = 0
        }
    }
}

DFS(0,0,1)
console.log(answer)