[백준 15649번/C++] N과 M (1) - 백트래킹

백트래킹을 처음봐서 써먹을게 브루트포스밖에 없어서 그걸 썼는데 시간초과 -> 백트래킹을 배워왔다.

 

• 백트래킹 : 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾음 
• 해가 아니어서 막힐 때 바로 포기 = 가지치기라고 하는데, 이를 통해 시간 단축 가능

보통 DFS에서 쓰인다. 처음에 이해하기 어려웠는데 맞은건 고정해두고 뒷부분만 바꿔가면서 진위 검증을 한다고 생각하니 이해가 됐다. 이해하고 그린 그림은 아래와 같다.

 

 DFS 함수에서 변수 정보와 배열 정보가 필요하기에 변수와 배열은 전역으로 생성했다.

이 방법이 카드 4장중 2장을 고르는 것에서는 브루트포스와 별 차이 없어보이는데, 만약 4장 중 3장을 고른다고 하면 

첫 선택에서 1/2를 고정해두고 뒤만 바꿔서 1/2/3, 1/2/4 출력->두번째 카드를 3으로 변경-> 반복문 돌며 세번째 카드 1/3/2, 1/3/4 출력 이런식으로 모든 수를 다시 찾지 않아도 돼서 빨라진다.

 

• 답

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

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

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    cin >> N >> M;
    
    DFS(0);

}