[Algorithm/Java][백준] 6603 로또

[백준] 6603 로또

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

문제 접근

백트래킹 방식으로 접근하여 재귀함수를 이용한 DFS를 이용하여 풀었다.
먼저 입력을 받은 숫자를 nums에 저장하고 사용했는지를 저장하기 위해서 nums와 같은 크기의 boolean 배열로 visited를 만들었다.
그리고 최종적으로 6개의 로또 번호를 저장하기 위한 배열 lotto를 만들었다.
결과가 오름차순으로 나와야 해서 lotto[cnt-1]과 nums[i]를 비교해서 탐색을 건너뛰도록 만들었다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ6603 {
    static int[] nums;
    static boolean[] visited;
    static int[] lotto = new int[6];
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            String[] input = br.readLine().split(" ");
            if(input[0].equals("0")) break;
            nums = new int[Integer.parseInt(input[0])];
            visited = new boolean[Integer.parseInt(input[0])];
            for(int i = 1; i<input.length; i++){
                nums[i-1] = Integer.parseInt(input[i]);
            }
            sb = new StringBuilder();
            generateLotto(0);
            System.out.println(sb.toString());
        }
    }
    static void generateLotto(int cnt){
        if(cnt == 6){
            for(int i = 0; i<lotto.length; i++){
                sb.append(lotto[i]);
                if(i!=lotto.length-1) sb.append(" ");
            }
            sb.append("\n");
        } else {
            for(int i = 0; i<nums.length; i++){
                if(!visited[i]){
                    if(cnt != 0 && lotto[cnt-1] > nums[i]) continue;
                    // 숫자를 로또에 포함했을 때
                    visited[i] = true;
                    lotto[cnt] = nums[i];
                    generateLotto(cnt+1);
                    // 숫자를 로또에 포함하지 않았을 때
                    visited[i] = false;
                }
            }
        }
    }
}

느낀 점

이제는 DFS와 BFS 기본 문제는 잘 풀 수 있게된 것 같다. 다른 블로그 풀이를 보니까 오름차순으로 하기 위해서 generateLotto함수에 cnt 파라미터 말고 시작 인덱스를 파라미터로 받아서 그 파라미터 부터 for문을 돌리는 방식이 있는데 그것도 좋은것 같다.