백트래킹 문제풀이 모음

강한친구·2022년 6월 22일

알고리즘 문제풀이 기법

목록 보기

26/27

15649

N까지의 자연수중에서 M개의 수를 중복없이 뽑는 문제이다.

정답

#include <iostream>
using namespace std;

int n, m;
int arr[9];
int visited[9] = {0, };

void pick(int cnt);

int main() {
    cin >> n >> m;
    pick(0);
}

void pick(int cnt) {
    if (cnt == m) {
        for (int i = 0; i< m; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            arr[cnt] = i;
            pick(cnt + 1);
            visited[i] = 0;
        }
    }
}

그다지 어렵지 않은 코드이다.

1부터 n까지 루프를 돌면서 특정 숫자가 방문하지 않은 숫자라면, visited를 1로 바꾸고 방문한걸로 처리한다.

cnt(자리수)를 한자리 늘리고 다시 pick 함수를 불러서 다음 자리수에 들어갈 값을 찾는다.

만약 cnt가 m에 도달했다면 더 이상 뽑을 필요가 없다. 따라서 cnt로 출력을 해주고 지금까지 썻던 visited를 모두 0으로 돌려놓고 for 루프를 하나 더 진행한체로 넘어간다.

4 2

1 
-> 
1 2
1 3
1 4
return 

2
->
2 1
2 3
2 4
return

3
->
3 1
3 2
3 4
return

4
-> 
4 1
4 2
4 3
return

이 순서로 진행된다.

15650

똑같이 N M 뽑기 문제지만 조건이 있다.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

즉
1 2
1 3
1 4
2 3
같은 순서로 고르라는 뜻이다.

정답

#include <vector>
#include <iostream>

using namespace std;
vector<int> vec;
void pick(int curr, int cnt, int n, int m);

int main() {
    int n, m;

    cin >> n >> m;
    pick(0,0,n,m);
}

void pick(int curr, int cnt, int n, int m) {
    if (cnt == m) {
        for (int elem : vec) {
            cout << elem << " ";
        }
        cout << "\n";
        return;
    }
    if (curr == n) {
        return;
    }

    vec.push_back(curr + 1);
    pick(curr + 1, cnt + 1, n, m);
    vec.pop_back();

    pick(curr + 1, cnt, n, m);
    return;
}

우선 종료조건은 이전 코드와 동일하다. cnt(자리수)가 m에 도달하면 출력 후 return 하는 방식이다.
다만 달라진점은, 현재 수보다 더 작은수는 고려하지 않아야하기 때문에, curr이라는 새로운 인자를 받아서 처리한다는 점이다.

현재수를 뽑은 경우
현재수를 뽑지 않고 넘기는 경우

두 경우로 나뉘게 된다.

뽑는 경우는 값 저장 리스트에 curr + 1을 저장하고, (0부터 시작함) 자리수와 curr을 1씩 늘린 후 재귀반복한다.

뽑지 않는 경우는 뽑지 않고 그대로 현재 수만 1 늘리고 재귀반복한다.

15651

위의 문제들과 비슷한데 이번에는 수가 중복되어도 그냥 뽑는 문제이다.

즉, 1번 유형에서 visited만 빼고 돌리면 되는 문제이다.

정답

#include <iostream>
#include <vector>
using namespace std;

int arr[7];
int n, m;
void pick(int cnt);

int main() {
    cin >> n >> m;
    pick(0);
}

void pick(int cnt) {
    if (cnt == m) {
        for (int i = 0; i < m; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= n; i++) {
        arr[cnt] = i;
        pick(cnt + 1);
    }
}

return을 하지 않기에 vec를 써서 푸는것보다는 array를 써서 푸는 방법이 더 간편한다.

15652

이전문제와 거의 유사한데 다른게 하나 있다면, 이전 문제에서는 비내림차순 조건이 추가되었다는점이다.

즉

에서

이렇게 변했다는 뜻이다. 2 1 3 1 3 2 같은 수는 뽑지 않는다.

정답

#include <iostream>
#include <vector>
using namespace std;

int arr[8] = {0, };
vector <int> vec;
int n, m;
void pick(int cnt);

int main() {
    cin >> n >> m;
    pick(0);
}

void pick(int cnt) {
    if (cnt == m) {
        for (int i = 0; i < m; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= n; i++ ) {
        if (arr[cnt - 1] <= i) {
            arr[cnt] = i;
            pick(cnt + 1);
        }
    }
}

중간에 조건을 잘못줘서 3 3을 해결하지 못했었다.

다른 풀이

for(int i = curr; i <= n; i++)
    {
            visited[i] = true;
            arr[cnt] = i;
            pick(i, cnt+1);
            visited[i] = false;
    }