백준 2529번: 부등호 (javascript, DFS, 백트래킹)

완전탐색을 해야하는 문제이며 나는 백트래킹을 이용해서 풀었다. 백트래킹은 DFS의 응용으로 방문하면 안되는 곳은 방문하지 않는 방식으로 탐색범위를 줄이며 탐색표시를 하고 다시 탐색표시를 해제함으로써 모든 범위를 탐색하는 알고리즘이다.

 

일전에 백트래킹으로 한 문제를 푼 적이 있는데 그 때는 queue에 방문 원소를 넣고 다시 빼고, 방문표시까지 해제하는 식으로 문제를 풀었었다. 그러나 꼭 queue에서 방문 원소를 빼야 하는 것은 아니라는 것을 깨닫고 이 글을 쓰게 되었다.

 

풀이는 다음과 같다. queue의 길이가 문제에서 주어진 숫자의 개수인 k+1이 되면 queue가 꽉찼다는 의미이므로 배열에 그 값을 넣고 함수를 끝낸다. 

 

그리고 백트래킹의 핵심은 backtract함수에서 보이듯이 for문으로 0~9까지를 돌면서 방문을 true로 하고 재귀함수를 실행, 그 후에 방문을 false로 함으로써 방문한 곳을 다시 방문하는데 있다.

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

const k = Number(input[0])
const inequality = input[1].split(' ')
let answer = []

function calculate(a,b,operation) {
    if (operation === '<') {
        return (a < b)
    } else {
        return (a > b)
    }
}

function backtrack(index, ans){
    if(index === k+1){
        answer.push(ans)
        return
    }
    for(let j=0; j<10; j++){
        if(!visited[j]){
            if(index === 0 || calculate(ans[index-1], j, inequality[index-1])){
                visited[j] = true
                backtrack(index+1, ans+String(j))
                visited[j] = false
            }
        }
    }
}

visited = new Array(10).fill(false)
backtrack(0, '')
answer.sort((a,b) => (a-b))
console.log(answer[answer.length-1])
console.log(answer[0])