[백준] 6603번 로또

문제

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

풀이과정

문제를 다 읽어본 후 [완전탐색] 문제라는걸 알았는데 DFS로 구현해야하는 문제인지는 잘 몰랐다. 풀이를 찾아서 DFS 구현을 봤는데 잘 이해가 가지 않는다.

DFS로 탐색을 하다가 6개가 모이면 출력을 하는 식인데 이러한 과정이 어떻게 진행되는지 정확하게 이해를 하지 못했다.

인프런 강의와 다른 강의를 좀 더 찾아서 DFS를 이용한 완탐 구현을 좀 더 공부하고 다시 풀어봐야겠다.

소스코드

#include <iostream>
#include <vector>

#define MAX_N 13
using namespace std;

int S[MAX_N];
int lotto[MAX_N];
int k;

void lotto_print()
{
    for (int i = 0; i < 6; i++) cout << lotto[i] << " ";
    cout << "\n";
}

void DFS(int start,int depth)
{
    if (depth == 6) lotto_print(); // 6개면 출력

    // 6개가 쌓이기 전에
    for (int i = start; i < k; i++)
    {
        lotto[depth] = S[i];
        DFS(i + 1, depth + 1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    do
    {
        cin >> k;

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

        DFS(0,0);

        cout << "\n";

    } while (k != 0);

    return 0;
}