[백준 6603] 로또

문제 출처: https://www.acmicpc.net/problem/6603

풀이

대놓고 백트래킹(방문,방문해제)을 쓰지않았음으로 dfs문제로도 볼 수 있다.

1. 입력받을 배열과 로또6자리를 저장할 수 있는 배열 선언

2. 시작점 0(index 0부터)과, 숫자 6개를 저장했다면 출력할 수 있게 dfs(start,cnt)함수를 만들어 호출한다.

3.  재귀함수 종료조건을 dfs내부에서, cnt=6이면 로또6자리가 쌓인것이므로 출력후 종료할 수 있게 작성한다.

4. 아래와 같이 작성하여 숫자6개의 모든 조합들을 탐색한다.

for (int i = start; i < k; i++)
	{
		lotto[cnt] = arr[i];
		dfs(i + 1, cnt + 1);
	}

i=5, cnt=5일 때 dfs를 수행하면 cnt=6이되므로 1 2 3 4 5 6을 출력후 함수를 빠져나오고 다시 돌아가 i=6으로 시작되어서 

lotto[5]= arr[6]으로 되어 1 2 3 4 5 6 7 즉, 맨 뒷자리부터 수정됨을 확인 할 수 있다.

코드

#include<iostream>
#include<vector>
using namespace std;
int k, arr[13];
void dfs(int start,int cnt);
int lotto[6];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	while (1)
	{
		cin >> k;
		int cnt = 1;
		if (k == 0)return 0;
		for (int i = 0; i < k; i++)
			cin >> arr[i];
		
		dfs(0,0);
		cout << '\n';
	}

}
void dfs(int start,int cnt)
{
	if (cnt == 6)
	{
		for (int i = 0; i < 6; i++)
		{
			cout << lotto[i] << " ";
		}
		cout << '\n';
		return;
	}
	for (int i = start; i < k; i++)
	{
		lotto[cnt] = arr[i];
		dfs(i + 1, cnt + 1);
	}
	
}

결과