15649번: N과 M(1)(백준 C++)

15649번: N과 M(1) 링크

코드

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

int n, m;
vector <int> v;
bool check[9] = {0, };


void solve(int cnt){
    if(m == cnt){
        for(int i=0; i<m; i++){
            cout << v[i] << " ";
        }
        cout << "\n";
    }
    else{
        for(int j=1; j<=n; j++){
            if(check[j] == 1) continue;
            check[j] = 1;
            v.push_back(j);
            solve(cnt+1);
            v.pop_back();
            check[j] = 0;
        }
    }
}
int main() {
    cin >> n >> m;
    solve(0);
    return 0;
}

사견

오랜만에 답지 보고 푼 문제이다.
접근 방법에 얼추 가까이는 갔었는데, 생각을 하나 잘못해서 계속 그 늪에 빠졌다.

이 문제를 해결하려면 깊이우선탐색을 사용해야하는데
탐색하면서 거치는 노드의 숫자를 따로 담아놓고 원하는 깊이까지 내려갔을때 다 읽어주고,
노드를 다시 빠져나오면서는 따로 담아둔 거에서 숫자를 빼줘야하는데...

깊이 탐색은 하면서 따로 노드의수를 안 담고 그 노드의 수만 출력하게 해서 헤맸었다.

예를 들어보자

N = 4 이고, M = 3 이다.

시작하면 선택지가 4개이다.

1 2 3 4

순서대로 가 보자, 우선 1을 선택한다. 1을 사용했다는 증거를 남긴다. (check[1] = True) 또한 지나온 목록에 '1'을 넣어준다. (v.push_back(1))

그 다음에도 일단은, 선택할 선택지 자체는 4개이다.

1 2 3 4

하지만, Check Array의 존재로 인해, 우리는 1을 사용했다는 것을 알고있다.
이렇게 Check Array에서 True 값을 가진 수는 Pass하면
이번에 선택할 수 있는 선택지는 3개가 된다.

2 3 4

여기서 2번을 선택하고 아까와 마찬가지로
Check Array 및 Vector의 값을 변경 및 추가한다.
(check[2] = True)
(v.push_back(2))

그 다음에 선택할 수 있는 선택지는?
원래는 4개지만, 현재 1, 2를 사용한 걸 알 고 있으므로...

3 4

2개이다.

여기서 3번을 선택한다.
(check[3] = True)
(v.push_back(3))

그 다음에는 선택할 필요가 없다. 왜?
이미 4개중에 3개를 골랐으니까.

3개가 다 채워졌으므로
우리는 지금까지 담아놓은 수를 담은 순서대로 읽어준다.

이후 다시 돌아와서

3번을 선택하기 이전으로 돌아간다, 즉
1 -> 2 -> ??
1을지나 2를 지나서 3번째 숫자를 다시 선택하게 되는것이다.
그렇다면 선택지가

3 4

인가?

아니다.

이미 우리가 3을 썼다는 것을 Check Array로 알기 때문이다.
해서 다시 우리가 선택할 선택지는 4가 되고
이를 골라서
1 2 4를 출력한다.

이를 계속 반복하면 된다.

그림이 없는 설명이라 상당히 이해하기 어렵다고 생각이 된다.
그런 분들은 따로 깊이우선탐색, 넓이우선탐색에 대해 찾아 보신 후, 백트래킹까지 찾아보시길 추천한다.