[BOJ] 백트래킹 1

📝15649번: N과 M (1)

문제 설명

N과 M (1)

해결 방법

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력해야 하므로 중복 여부를 체크하는 visited를 선언, N의 범위가 1부터 8까지므로 크기가 9인(인덱스 0 ~ 8) 배열을 선언한다. 모든 가능한 수의 조합을 출력해야 하므로 모든 노드를 방문하는 dfs로 해결한다. depth가 입력 받은 M과 같다면 배열에 들어있는 원소들을 출력한다. 해당 숫자를 방문했다면 visited 배열의 원소를 true로 표시한 후 배열에 넣고 재귀적으로 다음 depth로 들어간다.

💻소스코드

#include <iostream>

using namespace std;

int N, M;
int arr[9] = { 0, };
bool visited[9] = { false, };

void dfs(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; i++)
            cout << arr[i] << ' ';
        cout << "\n";
    } else {
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = i;
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
}

int main(void)
{
    // N과 M (1)
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    dfs(0);

    return 0;
}

---

📝15650번: N과 M (2)

문제 설명

N과 M (2)

해결 방법

dfs로 해결, 숫자들이 반드시 오름차순이어야 하므로 반복문에서 수의 시작을 num으로 설정했다. 재귀적으로 반복할 때 depth와 i를 1씩 증가시켜주고 depth가 입력 받은 M과 같다면 배열에 들어있는 원소들을 출력한다.

💻소스코드

#include <iostream>

using namespace std;

int N, M;
int arr[9] = { 0, };

void dfs(int depth, int num) {
    if (depth == M) {
        for (int i = 0; i < M; i++)
            cout << arr[i] << ' ';
        cout << "\n";
    }
    else {
        for (int i = num; i <= N; i++) {
            arr[depth] = i;
            dfs(depth + 1, i + 1);
        }
    }
}

int main()
{
    // N과 M (2)
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    dfs(0, 1);

    return 0;
}

---

📝15651번: N과 M (3)

문제 설명

N과 M (3)

해결 방법

dfs로 해결, 1부터 모든 가능한 수의 조합을 출력해야 하므로 배열의 인덱스(depth)에 해당하는 숫자들을 넣고 depth가 입력받은 M과 같다면 배열에 들어있는 원소들을 출력한다.

💻소스코드

#include <iostream>

using namespace std;

int arr[8] = { 0, };
int N, M;

void dfs(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; i++)
            cout << arr[i] << ' ';
        cout << "\n";
    }
    else {
        for (int i = 1; i <= N; i++) {
            arr[depth] = i;
            dfs(depth + 1);
        }
    }
}

int main()
{
    // N과 M (3)
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    dfs(0);

    return 0;
}

---

📝15652번: N과 M (4)

문제 설명

N과 M (4)

해결 방법

dfs로 해결, 오름차순으로 출력하되 하나의 출력에서 이전 depth에서의 숫자와 같아도 된다. 따라서 반복문에서 dfs를 수행할 때 num의 자리에 i를 그대로 넣는다. depth가 입력받은 M과 같다면 배열에 들어있는 원소들을 출력한다.

💻소스코드

#include <iostream>

using namespace std;

int N, M;
int arr[9] = { 0, };

void dfs(int depth, int num) {
    if (depth == M) {
        for (int i = 0; i < M; i++)
            cout << arr[i] << ' ';
        cout << '\n';
    }
    else {
        for (int i = num; i <= N; i++) {
            arr[depth] = i;
            dfs(depth + 1, i);
        }
    }
}

int main()
{
    // N과 M (4)
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    dfs(0, 1);

    return 0;
}

---

DFS는 말로 자세하게 설명하기가 정말 어려운 것 같다. 어떻게 진행되는지 과정을 한 번 들여다보면 이해가 간다.