[백준] 6603번 로또

 

 

문제

소스코드

 

#include<iostream>
#include<vector>
 
constexpr int MAX_SET = 28;
 
std::vector<std::vector<int>>S;
std::vector<int>V;
int K{};
bool visited[MAX_SET];
 
void BackTracking(int curr, int index) {
 
    if (curr > 6) {
        for (const auto& i : V) {
            std::cout << i << " ";
        }
        std::cout << "\n";
        return;
    }
 
    for (int i = 0; i < S[index].size(); ++i) {
        //방문여부가 false이면 다음값을 체크하자
        if (visited[i] == false) {
 
            //넣을려고 할때 앞에 숫자가 더 작으면 패스
            if (V.size() != 0) {
                if (S[index][i] < V[V.size() - 1])continue;
            }
 
            V.emplace_back(S[index][i]);
            visited[i] = true;
            BackTracking(curr + 1, index);
            //BackTracking 이후
            V.pop_back();
            visited[i] = false;
 
        }
    }
}
 
int main() {
 
    while (true) {
        std::cin >> K;
        std::vector<int>setLIst;
        if (K == 0)break;
 
 
        for (int i = 0; i < K; ++i) {
            int number{};
            std::cin >> number;
            setLIst.emplace_back(std::move(number));
        }
        S.emplace_back(setLIst);
 
    }
    for (int i = 0; i < S.size(); ++i) {
        BackTracking(1, i);
        std::cout << "\n";
    }
}

후기

이 문제를 해결하기 위한 키워드는 백 트래킹이다.

 

백 트래킹(Back Tracking)이란 깊이 우선 탐색(DFS)의 구조를 기반으로 문제를 푸는 전략으로 탐색을 진행했다가 더 갈 수가 없으면 되돌아가 다른 길을 찾는다고 해서 이름이 붙였으며 주로 재귀 함수로 구현을 한다.

 

모든 경우의 수를 찾기만 한다면 관련글에 있는 N과 M으로 도 통과할 수 있지만 여기에 추가적으로 오름차순 즉 다음에 나올 수가 앞에 있는 수보다 작으면 안 되기 때문에 25~27번째 줄에 예외를 처리해서 진행을 하였다.

 

 

출처 및 레퍼런스

문제 링크: https://www.acmicpc.net/problem/6603

Color Scripter:  https://colorscripter.com/

 

관련 글

[자료구조 알고리즘/탐색 알고리즘(Search)] - 백 트래킹(Backtracking)

[온라인 코딩/탐색(Search)] - [백준] 15649번 N과 M