[백준 BOJ][C++]6603번 로또 풀이: DFS

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

6603번: 로또

 

 이 문제는 DFS로 해결할 수 있습니다.

 

 입력이 오름차순으로 주어졌으니 다음 탐색할 번호는 현재 번호 다음 번호들만 탐색하면 됩니다. 

 

 기존 dfs와 크게 다른 것은 없지만, (n-1 - i) >= (5 - depth)라는 조건이 붙죠?

 

 n-1 : 숫자 배열의 마지막 index 

 i : 탐색할 번호의 index

 n-1 - i : 탐색할 번호 다음에 남은 수들의 개수

 5 - depth : 현재 depth 다음 depth에서 앞으로 추가해야할 수들의 개수

 

 문제에서 주어진 n=7, 1 2 3 4 5 6 7 을 예시로 들겠습니다. 

 

 1로 시작하는 수들을 고를 때, dfs(1, 1)로 시작합니다. 

 

 그럼 현재 수열 dfs_arr={1, } 입니다. 

 

 1 다음 수 들은 2, 3, 4, 5, 6, 7이 있죠!

 

 2를 먼저 보겠습니다. 2는 배열 arr 내에서 index가 1입니다. 

 

n-1-i = 7-1-1 = 5 입니다. 즉, 2 다음에 5개의 수가 더 남아있다는 뜻이죠.

5-depth = 5 - 1 입니다. 즉 2를 추가한 뒤에도 4개의 원소를 dfs_arr에 추가해야 한다는 뜻입니다. 

 

조건이 충족하죠? 이때 dfs_arr={1, 2, } 입니다. 

 

 

만약 1 다음에 4를 추가할 때는 어떨까요?

 

n-1-i = 7-1-3 = 3으로 4 다음에 남은 숫자는 3개이죠

하지만 5-depth = 5-1 = 4개이므로 4를 추가한 뒤에도 4개를 더 추가해주어야 하는데 4 다음에 숫자는 3개 밖에 남지 않으므로 4쪽으로는 탐색이 이루어지면 안 됩니다! 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>

using namespace std;

int n;
int arr[13];
int dfs_arr[6];
bool visit[13] = { false, };

void dfs(int idx, int depth) {

	if (depth == 6) {
		for (int i = 0; i < 6; i++)
			cout << dfs_arr[i] << " ";
		cout << endl;
		return;
	}

	for (int i = idx + 1; i < n; i++) {
		if (!visit[i] && (n - i - 1) >= (5 - depth)) {
			visit[i] = true;
			dfs_arr[depth] = arr[i];
			dfs(i, depth + 1);
			visit[i] = false;
		}
	}

}

int main(void) {

	while (true) {
		cin >> n;

		if (n == 0)
			break;

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

		for (int i = 0; i < n; i++) {
			memset(visit, false, sizeof(visit));
			dfs_arr[0] = arr[i];
			visit[i] = true;
			dfs(i, 1);
			visit[i] = false;
		}

		cout << endl;
	}

	return 0;
}