BOJ_6603 로또 [Java] (S2)

문제 설명

풀이

모든 가지의 수를 구하는데 오름차순이라는 조건이 걸려있다.

그렇기에 일단 최심부까지 들어가는 DFS를 해야된다고 일단 생각이 났다.

그리고 백트래킹을 통해 각각의 경우의 수를 모두 파악하려고 하였다.

 

하지만 DFS 인자와 시작을 어떻게 해야할지 잘몰라서 방황하다가, start를 기준으로 계속 올라가게 만들면 된다는 생각을 했다. 그리고 for문은 dfs를 돌다가 마지막 조건에 도달했을때 해야된다는 것도 여기서 깨닫게 되었다.

 

백트래킹은 순차적으로 접근하여서 사전순으로 나열하기 좋음

 

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] lis;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            String input = br.readLine();
            if(input.equals("0")){
                return;
            }
            StringTokenizer st = new StringTokenizer(input);
            N = Integer.parseInt(st.nextToken());
            lis = new int[N+1];
            visit = new boolean[N+1];
            for(int i =0; i<N; i++){
                lis[i] = Integer.parseInt(st.nextToken());
            }

            dfs(0,0); //DFS어떻게 시작하는지 확실하게 정리!!!
            System.out.println();
        }
    }

    private static void dfs(int start, int depth) {
        if(depth == 6){
            for (int i=0; i<N; i++){
                if(visit[i]){
                    System.out.print(lis[i] + " ");
                }
            }
            System.out.println();
        }
        else{ //이부분 중요!!!
            for(int i=start; i< N; i++){
                visit[i] = true;
                dfs(i+1,depth+1);
                visit[i] = false;
            }
        }
    }
}

 

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

6603번: 로또