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

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

15649번: N과 M (1)

---

📌 작성한 코드

// 15649
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 isused = new Array(N + 1).fill(false);

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

    for (let i = 1; i <= N; i++) {
        if (!isused[i]) {
            arr[k] = i;
            isused[i] = true;
            backTracking(k + 1);
            isused[i] = false;
        }
    }
};

backTracking(0);

 

📌 설명 

백트래킹을 통해 원하는 길이의 수열을 구하는 문제이다.

 

백트래킹을 처음 보았을 때는 dfs와 정말 비슷하게 생겼다는 생각이 들었고, 실제로 둘이 비슷하기도 하다.

dfs와 백트래킹의 차이점은 끝까지 탐색하느냐 아니면, 가지치기를 하느냐이다. dfs는 완전 탐색으로 모든 경우의 수를 다 탐색하지만 백트래킹은 도중에 답이 될 가능성이 없다고 하면 해당 가지를 버리고 다른 가지를 탐색한다. 밑의 블로그 설명을 통해 더 잘 이해할 수 있을 것이다. 

https://sojeong-lululala.tistory.com/184?category=1015520

[이진탐색] 깊이 우선 탐색[DFS]과 백트래킹[Backtracking] 차이점

 

이번 문제에서는 수열 내에 겹치는 숫자가 없어야 한다는 것 이외의 조건이 없기 때문에 해당 숫자가 이미 사용되었는지만(isused) 확인해주면 된다.

const backTracking = (k) => {
    if (k === M) {
        console.log(`${arr.join(" ")}`); // 원하는 길이 만큼 수열 요소를 구했으니 출력하고 리턴하기
        return;
    }

    for (let i = 1; i <= N; i++) {
        if (!isused[i]) { // 해당 숫자가 사용되지 않았다면 (수열에 이미 포함된 상태가 아니라면)
            arr[k] = i; // 현재 k 위치에 숫자 넣어주기(수열에 추가하기)
            isused[i] = true; // 사용 표시하기
            backTracking(k + 1); // 다음 숫자를 찾기 위해 백트래킹 재귀 
            isused[i] = false; // 사용 다했으니까 사용표시 해제하기
        }
    }
};

 

 

✅ 성공