(C++) - 백준(BOJ) 6603번 : 로또 (DFS) 답

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

[

6603번: 로또

문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는

www.acmicpc.net

](https://www.acmicpc.net/problem/6603)

간단한 Back tracking 문제였습니다.

• 풀이방법 : 정적 배열이용

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

  //DFS 문제입니다. 거꾸로 노드를 거슬러 올라가며 탐색해야하니 백트렉킹 전문 DFS를 사용했습니다. //DFS(DFS(DFS(node,depth)))... 이런 방식인 재귀함수로 풀었습니다. #include <iostream> using namespace std; int k; int c; int s[14]; //집합 int l[14]; //로또   void DFS(int node,int depth) {     if (depth == 7) //최종 깊이까지 탐색을 했다면 로또 번호 출력함     {         for (int i = 1; i <= 6; i++)          {             cout << l[i] << ' ';         }         cout << '\n';         return;     }     for (int i = node; i <= k; i++)//모든 노드를 하나씩 찍으며 DFS     {         l[depth] = s[i];           DFS(i + 1, depth + 1);     }   } int main() {     while (cin >> k && k)     {         for (int i = 1; i <= k; i++)             cin >> s[i];         DFS(1, 1);         cout << '\n';     } }

• 풀이방법2 : vector 이용

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

  #include <iostream> #include <vector> using namespace std; int k; vector <int> ans; vector <int> lotto; void dfs(int idx){     if(ans.size()==6){         for(int i = 0; i<6; i++){             cout << ans[i] << ' ';         }         cout <<'\n';         return;     }     for(int i = idx; i<k; i++){         ans.push_back(lotto[i]);         dfs(i+1);         ans.pop_back();     } } int main(){     while(cin >> k && k!=0){         lotto = vector<int>(k,0);         for(int i = 0; i<k; i++) cin >> lotto[i];         dfs(0);         cout << '\n';     } }