[C++] 백준 15652번 - N과 M(4) (백트래킹) 문제 풀이

#백준 15652번 N과 M(4)

 

 

백준 15652번 문제는 문제도 간단해서 언뜻 보기에는 쉬워 보이지만 백트래킹, 재귀에 관한 개념이 제대로 잡혀 있지 않다면 본인처럼 헤맬 수 있다.

 

 

문제 링크

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

15652번: N과 M (4)

알고리즘

dfs 함수는 재귀함수이고, 두 개의 파라미터를 가진다. num과 k인데, num은 1~N까지 숫자, 즉 출력되는 숫자라고 생각하면 된다. 그리고 변수 k는 배열의 길이이다.

 

배열의 길이를 파라미터로 갖는 이유는, 배열에 num을 저장하면서 M개가 됐을 때 그 배열을 출력하기 때문이다. 그것이 if(k==M) 문 코드이다.

 

흐름을 잠시만 예를 들어서 이해해보자면,

main함수에서 dfs(1,0)을 호출받고 dfs는 실행된다. 이때 else문 안에 있는 for문이 실행되면서 재귀함수가 계속 호출되는데 i=1인채로 k만 1씩 증가한채로 계속 호출된다. 그러면 어느순간 k==M을 만족하게 될텐데 그러면 if(k==M) 아래에 있는 for문을 통해 정해진 형식으로 숫자 한 줄이 출력된다.

 

그 다음이 중요한데, 그리고 그 함수는 끝나게 된다. 그러면 다시 바로 이전 재귀 호출된 for문으로 돌아와서 i=num일 때 돌았으니 i++되어서 i가 num+1일 때로 돌 것이다. 그런데 기억하는가? 이때의 k값은 바로 이전 재귀호출된 함수라 M값과 같다. 그러면 맨 마지막 숫자만 바뀐채로 ( 예를 들어, 1 1 1 에서 1 1 2로 ) 또 출력이 될 것이다. 그 다음에는 또 돌아와서 i++ 되어서 다음 for문에서 마지막 숫자만 또 하나 커진채로 바뀔 것이다. 이런 시슽템이 반복되면서 예제 출력과 같은 문자열이 완성되는 것이다.

 

만약 잘 이해가 안된다면 디버깅하면서 재귀 호출의 흐름을 명확하게 짚고 넘어가면 좋을 것이다.

 

코드

#include <iostream>
#define MAX 9

using namespace std;

int N,M;
int arr[MAX];

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

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

    return 0;
}

 

제출 결과