[JavaScript/백트래킹] 백준 실버 3 : 15650 - N과 M (2)

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

15650번: N과 M (2)

---

📌 작성한 코드 

// 15650
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
const input = fs.readFileSync(filePath).toString().trim();

const [N, M] = input.split(" ").map(Number);

const arr = new Array(M);

const backTracking = (at, depth) => {
    if (depth === M) {
        console.log(`${arr.join(" ")}`);
        return;
    }

    for (let i = at; i <= N; i++) {
        arr[depth] = i;
        backTracking(i + 1, depth + 1);
    }
};

backTracking(1, 0);

📌 풀이 

백트래킹을 이용해서 원하는 길이 만큼의 수열을 구하는 문제이다. 단, 수열은 오름차순으로 이루어져 있어야 한다.

N과 M(1) 문제에서 추가된 조건은 '오름차순'으로 정렬된 수열만 구하고 싶다는 것이다.

 

(1) 1번 방식대로 풀고 정렬하는 방법으로 풀면 안되는 이유

수열은 순서가 있는 숫자의 나열이기 때문에 순서가 다르면 다른 수열로 취급한다. 그래서 N과 M(1) 답을 보면 같은 수로 이뤄져있는데 다른 수열로 취급되는 것들이 보인다. 하지만 이번 문제에서는 오름 차순으로 정렬된 수열만 원한다. -> 즉 같은 수로 이뤄져 있는데 다른 수열로 취급되는 수열들이 없다는 것이다. 그래서 단순하게 (1)번의 방식대로 풀고 정렬하게 되면, 중복되는 수열이 존재하게 된다. 또한 정렬하는데 시간이 많이 소요된다는 단점도 존재한다.

 

(2) 수열의 이전 숫자보다 큰 숫자부터 탐색하기

그래서 이제 다음 수열에 들어갈 숫자를 찾을 때 수열의 이전 숫자보다 큰 숫자부터 탐색할 것이다. 그러기 위해 재귀 함수에 탐색하기 시작할 숫자의 번호를 같이 넣어서 재귀 함수를 작성해준다. 여기서 isUsed와 같이 방문 배열을 사용하지 않는 이유는 이전 숫자보다 큰 숫자만 탐색하고 있기 때문에 숫자를 이미 사용했을리가 없다. 무조건 처음 접근하는 숫자만 있기 때문에 따로 기록해주지 않아도 문제없이 답을 구할 수 있다. 

const backTracking = (at, depth) => { // at : 탐색 시작할 숫자
    if (depth === M) {
        console.log(`${arr.join(" ")}`);
        return;
    }

    for (let i = at; i <= N; i++) { // at부터 탐색 시작
        arr[depth] = i;
        backTracking(i + 1, depth + 1); // 현재 탐색한 숫자 다음 숫자 at으로 넘기기
    }
};

✅ 성공