[Backtracking] 백준 15651 N과 M 3단계 Node.js 구현하기

 

 

 

문제

 

문제링크

• 백준 15651 N과 M 3단계

 

 

 

 

이전 백트래킹 문제의 경우 중복되는 경우의 수를 모두 제거했지만, 이번 문제는 주옥을 허용한 모든 경우의 수를 표현합니다. 백트래킹은 DFS와 BFS 알고리즘과 같이 트리 구조상에 위치한 데이터를 검색할 수 있는 알고리즘입니다. 만약 특정 조건을 만족하는 경우 상위 노드로 이동하면서 검색을 계속 진행하게 됩니다. 

 

백준 15651 문제의 경우 트리 구조의 모든 노드를 탐색한 완전탐색 백트래킹 알고리즘을 사용합니다. 추가적으로 문제를 제출할 때 배열의 요소별로 출력을 진행하면 시간초과 오류가 뜨게 됩니다. JAVA에서는 StringBuilder를 사용해서 출력하지만 Node.js 환경에서는 string에 담아 한번에 출력해줘야 시간초과 오류를 해결하게 됩니다.

 

 

 

풀이

 

 

이 문제의 재귀 탈출 조건 값은 주어진 길이 M이 됩니다. 도달한 result 배열의 길이가 M이 되는 경우 상이ㅜ 노드로 이동하게 됩니다. 그리고는 다시 다른 노드로 이동하면서 모든 트리 구조의 노드들을 검색합니다.

 

1부터 인수를 증가하면서 N까지 반복문을 진행합니다. 요소를 result 배열에 추가하고 재귀함수를 호출합니다. 

for(let i=1; i<=N; i++){
    result.push(i);
    DFS();
    result.pop();
}

 

재귀 함수를 사용하는 건 반복해야 할 횟수를 특정하지 못하는 경우 유용하게 사용할 수 있습니다. 예를 들어 요소를 100까지 반복하면서 요소를 출력하는 경우 재귀함수를 사용해 간단하게 표현할 수 있습니다.

const result = [];

const recur = (n) =>{

    if(n === 100){
        result.push(n);
        console.log(result.join(' '));
        return;
    }
    result.push(n);
    recur(n+1);
}


recur(1);

 

다시 문제로 돌아가서 재귀 함수가 돌면서 result 배열의 길이가 주어진 인수인 M과 같아지는 경우(모든 경우의 수를 출력) 재귀함수는 종료되고, 이전 단계로 복귀하게 됩니다. 이 부분이 백트래킹의 핵심입니다. 백준에서 시간초과 문제 때문에 string 타입의 resArr에 데이터를 추가해 한번에 출력했습니다.

if(result.length === M){
    resStr += result.join(' ')
    resStr += '\n';
    return;
}

 

 

Node.js 코드

/*
    문제 : 백준 수 백트래킹 입문 3
    날짜 : 2022-06-12
    작성 : About-Tech
*/

const readline = require('readline');
const { stdin : input, stdout : output } = require('process');
const { arrayBuffer } = require('stream/consumers');

const rl = readline.createInterface({input, output});


rl.on('line', (line)=>{
    const input = line.split(' ').map((item)=>parseInt(item));
    const N = input[0];
    const M = input[1];
    
    const result = [];
    let resStr = '';

     // DFS 이용

    const DFS = () =>{
        // 배열 길이가 M인 경우 return
        if(result.length === M){
            resStr += result.join(' ')
            resStr += '\n';
            return;
        }

        // 배열을 순회하면서 DFS 돌리기
        for(let i=1; i<=N; i++){
            result.push(i);
            DFS();
            result.pop();
        
        }
    }

    DFS();

    console.log(resStr);

    rl.close();
})



rl.on('close',()=>{
    process.exit();
})

 

제출결과

 

 

 

[Algorithm] 백준 15649, 15650 JS 구현 ( 백트래킹 DFS 차이 )

 

[Algorithm] treeBFS 알고리즘 Javascript Node.js 구현하기

 

[Algorithm] 퀵 정렬(Quick Sort) Javascript, Node.js 구현하기 (백준 2751 수 정렬하기 2)