[백준 6603번] 로또

풀이

---

출력예시를 보면 마지막 숫자부터 바뀌는 것을 보면 DFS로 풀 수 있다는 것을 알 수 있다.

현재위치와 스택에 쌓인 카운트를 세주면서 방문여부를 체크해 주면 된다.

로직

1. 0번지에서 시작한다.

2. 0번지 방문을 체크하고, 카운트를 1 증가시켜준다.

3. 1번지로 이동한다.

4. 1번지 방문을 체크하고, 카운트를 1 증가시켜준다.

5. 1~4번 항목을 반복하여 카운트가 6인 경우 방문 배열을 체크하여 방문이 체크가 된 index만 출력한다.

6. 방문 체크를 해제해 주고, 카운트를 증가시키지 않은 상태에서 오른쪽으로 한칸 이동후 반복한다.

소스코드

---

#include <iostream>
using namespace std;
 
int n, arr[20], visit[20];
 
void select_fn(int cur, int cnt) {  // cur -> 현재 pos, cnt -> 쌓은 갯수
    if (cur == n && cnt == 6) {
        for (int i = 0; i < n; i++) { if (visit[i] == 1) { cout << arr[i] << " "; } }
        cout << '\n';
    }
    if (cur == n) return;
    visit[cur] = 1;
    select_fn(cur+1, cnt+1);  // 오른쪽으로 한칸이동, 쌓은갯수+1
    visit[cur] = 0;  // 위에서 방문을 완료했기에 방문 초기화
    select_fn(cur+1, cnt);  // 현재 위치만 오른쪽으로 한칸이동후 재탐색
}
 
int main() {
    while (1) {
        cin >> n;
        if (n == 0)
            return 0;
        else {
            for (int i = 0; i < n; i++) {
                cin >> arr[i];
            }
            visit[20] = { 0, }; //방문 초기화
            select_fn(0, 0);
        }
        cout << '\n';
    }
    return 0;
}

#include <iostream>
using namespace std;
 
int num[50], n, Stack[6], sp=0;
 
void push(int a) {
    Stack[sp++] = a;
}
 
int pop() {
    return Stack[--sp];
}
 
void lotto(int cur) {
    if (sp == 6) {
        for (int i = 0; i < 6; i++) {
            cout << Stack[i] << " ";
        }
        cout << '\n';
        return;
    }
    else {
        for (int i = cur; i < n; i++) {
            push(num[i]);
            lotto(i+1);
            pop();
        }
    }
}
 
int main() {
    while (1) {
        cin >> n;
        if (!n)
            break;
        else {
            for (int i = 0; i < n; i++) {
                cin >> num[i];
            }
            lotto(0);
            cout << '\n';
        }
    }
    return 0;
}