6603_로또 (DFS 백트래킹)

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

#include <iostream>
#include <vector>
using namespace std;

int out[13];
int n = -1;
int arr[13];

void lotto(int depth, int count)
{
	if(depth == 6)
	{
		for(int i = 0; i < depth; i++)
			cout << out[i] << " ";
		cout << endl;
		return ;
	}
	
	for(int i = count; i < n; i++)
	{
		out[depth] = arr[i];
		lotto(depth + 1, i + 1);
	}
}

int main(void)
{
	while(1)
	{
		if(n == 0)
			break;
		
		cin >> n;
		for(int i = 0; i < n; i++)
			cin >> arr[i];
		
		lotto(0, 0);
		cout << endl;
	}
	
	return 0;
}

 

6603_lotto의 문제풀이다. 인터넷 찬스를 이용해 풀었다.

 

DFS를 통해 6개를 돌고 그 후 백트래킹을 통해 돌지 않은 숫자를 돈다고 한다.

 

처음에는 이해가 되지 않아 그림을 그림으로써 이해했다.

 

각각의 반복분은 정해진 depth(깊이)에서만 반복을 돌면서 오름차순으로 올라가면 배열의 숫자에 접근한다.

 

그래서 depth == 6 일 때는 lotto의 인덱스 값은 5까지므로 depth가 6일때는 출력만을 담당한다고 생각하면 된다.

 

 

그림을 예로 들면 만일 6까지 간다음 lotto함수를 통해 한단계 깊이 내려가 출력한다음, 재귀를 통해 돌아간다음 i가 5에서 6으로 반복문을 진행하면서 아직 방문하지 않은 숫자에 가게 되는 것이다. 7이 배열의 종점이므로 7에서 방문할 곳이 없으므로 이제 7은 고정인 상태이다.

 

그러므로, 재귀를 통해 depth를 -1 시킨 곳에서 다시한번 진행하는 것이다. 그렇다면 여기서 질문이 생긴다.

 

'그러면 7 이 연속으로 나올 수도 있지 않을까?'

 

그러한 출력 값이 안 나오는 이유는 i = count 라고 변수를 선언했기 때문에, depth = 4 인곳에서 i = 6이 나와버리면 lotto함수를 통해 한칸 내려가도 반복문이 작동하지 않아 lotto[5]에 값을 넣지 못한다.

 

그렇기 때문에 같은 숫자가 연속으로 나오지 않는 것이다.