[백준 - 6603] 로또 - Java

문제 설명

 

6603번: 로또

 

풀이 회고

우선 해당 문제에서 요구하는 것은 49가지 수(1~49) 중 임의의(7~12개의) 주어진 수들의 집합에서 6개의 수를 골라 만들 수 있는 경우의 수입니다. 즉, 주어진 수들에 대해 6개의 조합을 구하는 것입니다. 자바를 통해 조합을 구할 수 있는 방법에는 여러가지 방법이 있겠지만, 대표적으로 백트래킹을 이용하는 방법과 재귀함수를 이용하는 방법이 있습니다.

 

저 같은 경우에는 평상시 익숙한 '재귀함수'를 이용하여 문제에 접근해보았는데, DFS 탐색하는 방법과 상당히 유사했습니다. 이를 위해 필요한 자원으로는 선택한 수를 나타내기 위한 boolean형 배열 visited와 주어진 수들의 집합의 범위를 초과하지 않도록 제한하기 위한 정수 depth 그리고 6개의 수를 고르는 것을 카운팅(counting)하기 위한 정수 cnt 였습니다. 탐색 전 visited는 최초에 모두 false로 처리되어있으며, depth는 0, cnt는 0으로 초기화합니다.

 

            boolean[] choices = new boolean[sizeOfLotto];
            dfs(choices, 0, 0);
            // 인자 1: 선택한 수들의 배열 choices, 인자 2: depth, 인자 3: cnt

 

우선 주어진 수들의 집합을 탐색(6개의 수를 선택) 처리를 위해 우선 해당 수를 선택(choices[depth] = true)한 경우를 고려하여 재귀 호출 시 cnt + 1을 인자로 주도록 했고, 해당 수를 선택하지 않은(다시 choices[depth] = false) 경우를 고려하여 재귀 호출 시 cnt를 인자로 주도록 했습니다. 이때 매번 재귀 호출 시 depth를 1씩 증가시켜주는데, 이는 앞서 언급했듯이 주어진 수들의 집합 범위를 초과하여 탐색하지 않도록 하기 위함입니다. 또한 6개의 수를 모두 고른 경우 더이상 탐색할 필요 없으므로 뽑은 6개의 수를 출력한 뒤 return 시키도록 했습니다.

 

    public static void dfs(boolean[] choices, int depth, int cnt) {
        if (cnt == 6) {
            print(choices);
            return;
        }

        if (depth == sizeOfLotto) {
            return;
        }

        choices[depth] = true;
        dfs(choices, depth + 1, cnt + 1);
        choices[depth] = false;
        dfs(choices, depth + 1, cnt);
    }

 

 

전체 소스 코드

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

class Main {

    static int sizeOfLotto;
    static int[] lottoNumbers;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        sizeOfLotto = Integer.parseInt(st.nextToken());

        while (true) {
            lottoNumbers = new int[sizeOfLotto];
            for (int i = 0; i < sizeOfLotto; i++) {
                lottoNumbers[i] = Integer.parseInt(st.nextToken());
            }

            boolean[] choices = new boolean[sizeOfLotto];
            dfs(choices, 0, 0);

            st = new StringTokenizer(br.readLine());
            sizeOfLotto = Integer.parseInt(st.nextToken());
            if (sizeOfLotto == 0) break;
            else System.out.println();
        }
    }

    public static void dfs(boolean[] choices, int depth, int cnt) {
        if (cnt == 6) {
            print(choices);
            return;
        }

        if (depth == sizeOfLotto) {
            return;
        }

        choices[depth] = true;
        dfs(choices, depth + 1, cnt + 1);
        choices[depth] = false;
        dfs(choices, depth + 1, cnt);
    }

    public static void print(boolean[] visited) {
        for (int i = 0; i < visited.length; i++) {
            if (visited[i]) {
                System.out.printf("%d ", lottoNumbers[i]);
            }
        }
        System.out.println();
    }
}

 

 

참고자료

• https://www.acmicpc.net/problem/6603
• https://minhamina.tistory.com/38