15649 C++ 백트래킹 문제 풀이

오늘은 백트래킹에 대해서 공부하기 위해 가장 위에 있는 문제를 풀어보기로 했다. 백트래킹이라는 이론 자체를 처음 접하기 때문에 가장 쉬운 문제를 풀기로 했다.

 

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

15649번: N과 M (1)

 

---

 

문제 설명

 

자연수 N과 M이 주어졌을 때 N까지의 숫자 중 M개를 선택해서 만들 수 있는 모든 수열을 나열하는 것이다. 보통 이런 문제는 경우의 수가 몇 개인지를 맞추는 경우면 간단히 다이나믹 프로그래밍을 사용하면 되는데, 이 문제는 직접 하나 하나 출력을 해줘야 해서 고려해야 할 부분이 많다고 느꼈다. 그런데 풀이 방법을 알고 나면 생각보다 간단히 풀 수 있는 문제라는 것을 알게 된다. 하지만 문제 풀이를 위해서 for문을 중첩하고 재귀를 사용해 보는 과정이 문제 풀이에 대한 이해도를 향상하는데 도움이 되니 가능하면 시간을 들여서 풀이해보는 시간을 가지면 좋겠다.

 

 

문제 풀이

 

우선 출력 결과에서 특징을 살펴보면 각 경우는 1~N까지의 숫자가 일정 횟수만큼 반복한다. 그러므로 for문을 활용해서 반복을 해주어야 하는 구간이 있음을 알 수 있다. 그리고 앞 자리 숫자는 고정인채 뒷 자리의 숫자만 바뀌는 구조를 보고 깊이 우선 탐색법을 떠올릴 수 있다.

 

 

전체 코드

 

#include <iostream>

using namespace std;

int arr[10];
int check[10] = {0, };
int N, M;

void func(int dep)
{
    if(dep==M)
    {
        for(int i=0; i<M; i++)
        {
            cout << arr[i] << " ";
        }
        cout << endl;
        return;
    }
    else
    {
        for(int i=1; i<=N; i++)
        {
            if(!check[i])
            {
                check[i] = true;
                arr[dep] = i;
                func(dep+1);
                check[i] = false;
            }
        }
    }
}

int main()
{
    cin >> N >> M;
    
    func(0);
    
    return 0;
}

 

 

답을 저장할 배열 arr과 방문을 확인 할 배열 check를 활용한다. 코드에서 확인할 수 있듯이 깊이 우선 탐색법을 활용해 arr을 M자리까지 채우고 깊이가 M에 도달하면 그대로 arr을 출력한다. 그리고 출력 후에는 다시 check했던 위치를 false로 바꾸어 다른 경우의 수를 만들어 다시 arr을 출력한다.

 

---

 

이 문제의 핵심은 방문 내역을 false로 변경하고, 해당 부분의 다른 경우의 수를 찾는 것이다. for문을 활용해서 숫자가 이미 arr에 있는지 확인하는 방법도 있겠지만, 이 방법을 활용하면 시간 효율성을 더 높일 수 있다.