[BOJ알고리즘, C++]#6603_로또, DFS, 백트래킹, 순열 백트래킹

 

#1. 문제

 

6603번: 로또

 

---

 

#2. 풀이

 

1. 백트래킹

 

[알고리즘]#6_백 트래킹

백트래킹은 문제 해결을 위해 여러 후보책들을 점진적으로 탐색하며, 현재 선택한 경로가 해결으로 이어질 수 없다고 판단되면, 이전 단계로 돌아가 다른 경로에 대한 탐색을 시도하는 방법입니다. 

 

2. 순열 유형의 백트래킹!

1. 먼저, 백트래킹 방식을 결정해야합니다. k개의 수를 골라 그 순서에 따라서 다른 경우의 수가 만들어지는 '순열(nPr)'입니다.
2. 백트래킹의 종료 조건을 먼저 설정합니다. 종료 조건은 조합 목록에 총 6개의 원소가 있을 경우 종료되며, 종료되는 시점에 각 원소를 차례대로 출력하고 종료해줍니다.
3. 백트래킹을 위한 DFS를 정의합니다. 이때, 다음 후보를 '시작' 인덱스로 하는 DFS를 재귀적으로 호출하는 방식입니다. 이때, 현재 다음 후보에 대한 재귀 호출을 수행하고 난 뒤에 해당 후보의 방문 여부를 다시 'false'로 변경하고, 정답 목록에서 제거해줍니다.

 

---

 

#3. 코드

/*
    [문제] : 백트래킹 활용 조합 문제
    [설명]
            1. DFS 구현
            2. 현재 노드가 비 방문 노드일 경우, DSF 탐색 수행 후 방문 여부 초기화와 현재 노드에 대한 결과 값 롤백
            3. 현재 노드가 방문 노드일 경우, 다음 후보 경로 탐색
*/

#include <iostream>
#include <vector>
using namespace std;

#define MAX 13

int K;
int S[MAX];
vector<bool> visited;

void dfs(int start, int cnt, vector<int>& ans)
{
    if(cnt == 6) // #1. 6개의 숫자를 골랐을 때 출력
    {
        for(int i = 0; i < 6; ++i)
            cout << ans[i] << ' ';
        cout << '\n';
        return;
    }

    for(int i = start; i < K; ++i) // #3. 이전에 선택한 숫자 다음부터 탐색 시작
    {
        if(!visited[i])
        {
            visited[i] = true;
            ans.push_back(S[i]);
            dfs(i + 1, cnt + 1, ans); // #2. dfs 재귀 호출 시 ans 전달
            visited[i] = false;
            ans.pop_back();
        }
    }
}

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

    while(true)
    {
        cin >> K;

        if(K == 0)
            break;

        for(int i = 0; i < K; ++i)
        {
            cin >> S[i];
        }

        visited.resize(K, false);
        vector<int> ans;

        dfs(0, 0, ans); // 초기 start 인덱스와 cnt를 0으로 설정

        cout << '\n'; // 각 테스트 케이스 사이에 빈 줄 출력
    }

    return 0;
}

 

---