[Silver 3] 15650번 N과 M (2)

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

15650번: N과 M (2)

 

이 문제는 DFS를 통해 해결해야한다.

 

알고리즘은 다음과 같다.

1. DFS를 1부터 0번째 수열을 먼저 검사한다. (모든 수열은 1부터 시작함)
2. M의 자리까지 DFS를 수행하였다면, 배열을 출력하고 DFS를 종료한다.
3. DFS를 수행할 num부터 N까지 반복을 수행하며, 방문하지 않은 수라면 배열에 i를 저장한다.
4. i를 통해 수열의 순서 번호를 증가시키며 DFS를 수행하고, 방문 표시를 초기화한다.

알고리즘에 따른 결과는 다음과 같다.

• N과 M이 아래와 같이 입력되었을 경우

4 2

 

위와 같은 그림으로 알고리즘이 흘러간다.

요약한다면, 첫번째 호출에 의해 첫번째 자리가 저장되고, 두번째 호출에 의해 두번째 자리가 저장, 세번째 호출에 의해 수열이 출력된다.

 

#include <iostream>
using namespace std;

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

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

int main() {
    cin >> N >> M;
    dfs(1,0);
}