[백준] 6603 로또 (JAVA)

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

위의 문제는 DFS를 이용한 백트랙킹으로 풀수있다. 처음에는 문제를 계속 풀려고 해도 풀리지가 않아서 타 블로그의 글을 보았다. 그럼에도 잘 이해가 가지않아서 혼자 연습장에 끄적거리보기도 하고 유튜브에 강의를 찾아보기도 하였다.

그러던 중 정말 크게 도움이 된 강의의 주소를 올려놓겠다.

https://www.youtube.com/watch?v=Ar40zcPoKEI - 코드없는 프로그래밍님의 강의이다.

 

아래의 코드를 통해서 내가 몰랐던것들과 새로 이해한것에 대해서 설명을 하겠다.

전역으로는 ary(원소들의 집합), k(집합의 크기), skip(현재 선택한 원소들에 대해서 나타내는 배열)과 출력을 할때 쓰일BufferedWriter를 선언했다.

  

 우선 main메소드에 있는 내용들에 대해서는 별다를게 없으니 넘어가고 DFS메소드에 대해서 설명하자면

앞에 있는 if문은 현재 선택한 (skip배열에 true라고 선택되어있는) 원소들의 수가 6개, 즉 문제에서 말하는 6개를 전부

골랐다면 현재 선택한 원소들을 출력하는 역할을 한다.

 

 그리고 그밑에 있는 for문은 DFS함수의 파라미터로 받은 start와 count를 하나씩 더해가며 재귀형식으로 돌린다.

나는 여기서 첫번째 인자와 두번째 인자가 정확히 무슨 역할을 하는지 몰랐는데 위의 강의를 보고 이해가 되었다.

첫번째 인자인 start는 강의를 보기전에는 집합속 원소들의 인덱스라고 생각을 했는데 그것이 아니라 집합의 인자들이 들어갈 자리의 인덱스 번호였다. 이것이 조금 이해가 안될수도 있는데, 뒤에있는 count까지 설명하고 다시한번 설명하겠디. count는 현재 내가 선택한, 즉 집합속 인자들이 몇개가 선택 되었는지 알려주는 변수이다. 

 

이해가 갈지 모르겠다. 다시 조금더 쉽게 설명하면 위의 start는 문제에서 6개의 인자가 들어갈 자리들의 인덱스를 나타내는 자리이고 DFS(strat+1, count+1)의 코드중 위의 있는 skip[i] = true는 집합의 i번째의 인자를 선택했다는 말이다. 그러므로 다음 start(로또의 자리의 번호라고 생각하면 될것 같다.)로 넘어가게 되는것이고 count(현재 로또의 몇번째 자리까지 차있는지)또한 1을 더해준다. 

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int k;
    static int[] ary;
    static boolean[] skip;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        while(true){
            st = new StringTokenizer(br.readLine(), " ");
            k= Integer.parseInt(st.nextToken());

            if(k==0)
                break;

            ary = new int[k];
            skip = new boolean[k];

            for(int i=0 ; i<k; i++)
                ary[i] = Integer.parseInt(st.nextToken());

            DFS(0, 0);
            bw.write("\n");
        }

        bw.flush();
        bw.close();
    }

    public static void DFS(int start, int count) throws IOException{
        if(count == 6) {
            for (int i = 0; i < k; i++)
                if (skip[i])
                    bw.write(ary[i] + " ");
            bw.write("\n");
        }
        for(int i=start; i<k; i++){
            skip[i] = true;
            DFS(i+1, count+1);
            skip[i] = false;
        }



    }
}