[백준] 6603번: 로또(dfs, 백트래킹)

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

6603번: 로또

 

코드

import java.util.Scanner;

public class Main {

	static int[] arr;
	static boolean[] visit;
	static int N;

	public static void dfs(int start, int depth) {
		if(depth == 6) {	// 탈출 조건(출력)
			for(int i=0; i<N; i++) {
				if(visit[i] == true) {	// 탐색된곳 => 출력
					System.out.print(arr[i] + " ");
				}
			}
			System.out.println();
                        return;	// 재귀 함수 종료

		}
		
		for(int i=start; i<N; i++) {
			visit[i] = true;	// 방문한 곳 체크
			dfs(i+1, depth+1);	// 재귀호출, 하나의 깊이를 탐색 후 => 다음 호출시 깊이+1
			visit[i] = false;	// 초기화
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(true) {
			N = scan.nextInt();
			arr = new int[N];
			visit = new boolean[N];
			
			if(N == 0)
				break;
			
			for(int i=0; i<N; i++) {
				arr[i] = scan.nextInt();
			}
			
			dfs(0, 0);
			System.out.println();
		}
		
		scan.close();
	}

}

풀이

주어진 숫자중(6개 ~ 13개) 가능한 모든 경우의수를 출력하는 문제이다.

집합 S는 오름차순으로 주어지고, S에 포함되는 수를 6개씩 가능한 모든 경우를 출력한다.

깊이가 6(6개 선택)이 될 때 까지 dfs를 계속 돌린다. 

깊이가 6일때 

dfs를 통해 깊이를 탐색하고, 깊이가 6이 됐을때(6개 선택) 백트래킹을 통해 고르지 않은 다음 번호를 고른다.

아래의 그림으로 표현할 수 있다.

 

input - [1, 2, 3, 4, 5, 6, 7]

 

처음 고를 수 있는 경우 - {1, 2, 3, 4, 5, 6}

다음은 6에서 백트래킹을 후 7을 방문하면 - {1, 2, 3, 4, 5, 7}

그 다음은 5에서 백트래킹 후 6을 방문할 수 있다. - {1, 2, 3, 4, 6, 7}