백준 6603번 로또 문제 풀이

매주 진행중인 알고리즘 공부 중 오늘은 백준 6603번 DFS와 백트래킹 문제를 풀어보자.

#문제
https://www.acmicpc.net/problem/6603

#풀이과정

사용자로 부터 로또번호를 생성할 번호의 개수 k를 입력받고 입력받은 k개의 숫자를 이용하여 로또를 오름차순으로 6개짜리 배열을 만들어 출력해야한다.

처음에 문제를 보자마자 재귀를 써야겠다는 생각은 하였지만 백트래킹을 써야하는지는 감이 오지 않아서 고민을 많이 했다.

시작점을 0번째 부터 로또를 딱 만들수 있는 크기인 k - 5번까지 사용하는 반복문을 만들어서 배열을 만든다.

그리고 findLottoNum 메소드에 현재 인덱스와 만들고 있는 String값을 전달해준다. 그럼 현재 인덱스 바로 앞에 위치할 숫자를 구해서 String에 붙혀서 출력해주는데 여기서 핵심은 밑에 cnt--이다. 이 부분을 붙힘으로써 백트래킹을 하여 모든 경우를 구하게 된다.

참 설명하기가 쉽지는 않지만 소스를 보면 짧아서 금방 이해할 수 있다. 알고리즘을 많이 더 접해볼수록 쉽게 풀수 있는 문제들이 많은 것 같다. 더 공부하자.

자세한 소스코드는 여기서 확인 가능하다. https://github.com/weduls/algorithm

package test;
 
import java.util.Scanner;
 
public class WedulDfs {
    private static StringBuilder sb = new StringBuilder();
    private static int cnt;
    private static int k;
    private static int arr[];
    
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        
        while ((k = in.nextInt()) != 0) {
            // 배열 초기화
            arr = new int[13];
            
            for (int i = 0; i < k; i++) {
                arr[i] = in.nextInt();
            }
 
            // 로또 번호가 최소 6개이므로 k - 5 번째 까지만 처음 시작이 가능
            for (int i = 0; i < k - 5 ; i++) {
                cnt = 1;
                findLottoNum(i, String.valueOf(arr[i]));
            }
            
            // 결과 출력 및 sb 초기화
            System.out.print(sb.append("\n").toString());
            sb = new StringBuilder();
        }
 
        in.close();
    }
 
    public static void findLottoNum(int index, String str) {
        if (6 == cnt) {
            sb.append(str + "\n");
        } else {
            for (int i = index + 1; i < k; i++) {
                cnt++;
                findLottoNum(i, str + " " + arr[i]);
            }
        }
        
        // 백 트레킹 (하나씩 건너 뛰면서 가능한지 여부 확인)
        cnt--; 
    }
}