[백준 / BOJ] - 15649번 N과 M(1) C++ 풀이

---

 

백준 - 단계별로 풀어보기 [15649] 

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

 

문제

 

 

풀이

 

조합의 개수를 구하는 문제이므로, dfs를 활용하여 풀이가 가능하다.

각 숫자는 순열에서 딱 한번만 사용되므로, 각 숫자를 인덱스로 가지는 bool형 배열인 visited를 선언하고,

해당 숫자를 뽑았는지 유무를 저장한다. 

숫자를 앞에서부터 한개씩 뽑아가면서 visited가 M개만큼 true가 되면, 출력을 해주는 재귀함수를 활용하면 된다.

 

 

코드

 

#include <iostream>
#define MAX 9
using namespace std;

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

void dfs(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])
        {
            visited[i] = true;
            arr[cnt] = i;
            dfs(cnt+1);
            visited[i] = false;
        }
    }
}

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

 

평가

 

dfs를 활용하여 순열을 구할 수 있다는 것을 알아두고 dfs를 통한 백트래킹 방식을 이해해두면 좋을 것 같다.

또한 재귀적으로 함수를 어떻게 작성해야 백트래킹이 가능한지를 충분히 고려해야 풀이가 가능한 문제이다.