[백준] 0927 오늘의 문제 풀이📚

대망의 백트래킹 문제를 풀어봤다..

일단 뭔가 백트래킹도 기초 문제를 보니

어느 정도 정해진 틀을 지켜가면서 응용이 될 것 같은 느낌.

일단 기초 문제들을 열심히 풀면서(풀이를 보면서 ㅎㅎ;) 기본 틀이 되는 코드를 좀 체화시켜야겠다.

 

1. N과 M (1)

문제 링크

 

a. 풀이 1

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const line = input[0].split(' ');
    const N = +line[0];
    const M = +line[1];

    const arr = new Array(M).fill(0); 
    const isUsed = new Array(N).fill(0); 

    function backtracking(k) {
        if(k === M) {
            let str = "";
            for(let i = 0; i < M; i++) {
                str += `${arr[i]} `;
            }
            console.log(str);
            return;
        }

        for(let i = 0; i < N; i++) {
            if(!isUsed[i]) {
                arr[k] = i + 1; 
                isUsed[i] = 1;
                backtracking(k + 1); 
                isUsed[i] = 0; 
            }
        }
    }

    backtracking(0);
});

 

b. 풀이 2

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const line = input[0].split(' ');
    const N = +line[0];
    const M = +line[1];

    const arr = []; 
    const isUsed = new Array(N).fill(0);

    function backtracking(k) {
        if(k === M) {
            console.log(arr.join(' '));
            return;
        }

        for(let i = 0; i < N; i++) {
            if(!isUsed[i]) {
                isUsed[i] = 1;
                arr.push(i + 1);
                backtracking(k + 1);
                arr.pop();
                isUsed[i] = 0;
            }
        }
    }

    backtracking(0);
});

첫 번째 풀이는 선택한 원소들을 그냥 배열에 담았다.

두 번째 풀이는 선택한 원소들을 스택에 push & pop 해주면서

DFS와 동일한 방식으로 백트래킹을 하는 듯.

사실 배열, 스택만 다르고 둘다 DFS 방식인 것 같기도 하다.

 

그리고 출력하는 방식도 join을 이용해서 한 번에 출력했는데, 약간 더 빠르게 나왔다.

스택 때문인건가 join 때문인건가