[BOJ] C++ 6603: 로또 - 일반적인 BFS

6603번: 로또

예

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

ans :
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

---

백트래킹에 대한 설명 없이 바로 풀이를 할 예정입니다. 기본 백트래킹 코드를 잘 모르거나 백트래킹이 익숙하지 않으면 아래 게시글을 꼭 읽어보길 바랍니다!!

[알고리즘] 백트래킹 - 재귀를 통한 구현과 응용 문제

---

문제를 정리하면 중복 없이 오름차순으로 6개의 숫자를 선택하면 된다. N과 M 시리즈에 있던 문제와 상당히 유사하고 차이점은 6개만 고르면 된다는 것이다. 이번에는 바킹독님의 코드를 보면서 최적화를 좀 많이 시켰다. 기존에는 답을 저장할 res배열을 pair형으로 선언해서 이전 항의 index를 넘겨줬다면 이번에는 아예 함수에서 cur을 통해 넘겨줬다.

 

덕분에 visited 배열을 통해 중복 검사를 하지 않고 1 2 3 4 5 6 7을 예시로 들면 2까지 방문했다면 2를 부모로 하는 트리의 자식들은 2 다음의 숫자부터 검사하면 따로 중복 검사를 할 필요가 없다.

/** BackTracking 15663 N과 M (9) **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int arr[10];
int res[10];
bool visited[10];
int n, m;

void func(int k)
{
    if (k == m)
    {
        for (int i = 0; i < m; i++)
            cout << res[i] << ' ';
        cout << '\n';
        return;
    }
    int temp = 0;
    for (int i = 0; i < n; i++)
    {
        if (!visited[i] && temp != arr[i])
        {
            temp = arr[i];
            res[k] = arr[i];
            visited[i] = true;
            func(k + 1);
            visited[i] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);

    func(0);
}