[JAVA] 백준 6603. 로또(DFS) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다.

오늘은 DFS를 이용한 문제를 풀어볼 예정입니다.

---

1. 문제

사진을 클릭하면 문제 페이지로 이동합니다

 

2. 입출력 예제

 

3. 접근

 쉽게 말하면 로또 번호 1부터 49까지의 수 중에서 k개 (6 < k < 13)를 뽑아 집합 S라고 가정하고 이후 집합 S에서 6개를 뽑았을 때, 나올 수 있는 모든 수를 출력하는 문제입니다.

 전형적인 "조합(Combination)" 문제라고 할 수 있습니다.

 조합에서도 요소의 중복 가능 여부에 따라 DFS 반복문 코드가 달라지니 유의합시다.

 

-- Tip --

 뽑은 6개의 숫자들이 다른 연산에 필요하다면 List에 저장해서 활용합시다. 하지만 이 문제처럼 출력만 할 뿐이라면 StringBuilder를 통해 출력하는 것이 List를 쓴 것보다 빠릅니다.

 

4. 로직 (조합)

 이후에 조합과 순열에 대한 게시글을 따로 작성해서 링크로 대체하도록 하겠습니다.

 

5. 코드

1. StringBuilder 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
    static int k;
    static int[] lottoArr;
    static boolean[] visited;
    static final int SELECT = 6;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        
        while(true) {
            k = Integer.parseInt(st.nextToken());
            if(k == 0) break;
            lottoArr = new int[k];
            
            for(int i = 0; i < k; i++) {
                lottoArr[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine().trim());
            StringBuilder sb = new StringBuilder();
            visited = new boolean[k];
            solveDFS(sb, 0, 0);
            System.out.println(sb);
        }
    }
    
    private static void solveDFS(StringBuilder sb, int idx, int cnt) {
        if(cnt == SELECT) {
            for(int i = 0; i < visited.length; i++) {
                if(visited[i]) {                    
                    sb.append(lottoArr[i] +  " ");
                }
            }
            sb.append("\n");
            return;
        }
        for(int i = idx; i < lottoArr.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                solveDFS(sb, i, cnt + 1);
                visited[i] = false;
            }
        }
    }
}
 

 

2. LinkedList 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
    static int k;
    static int[] lottoArr;
    static boolean[] visited;
    static final int SELECT = 6;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        
        while(true) {
            k = Integer.parseInt(st.nextToken());
            if(k == 0) break;
            lottoArr = new int[k];
            
            for(int i = 0; i < k; i++) {
                lottoArr[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine().trim());
            visited = new boolean[k];
            LinkedList<Integer> resArr = new LinkedList<>();
            solveDFS(0, resArr);
            System.out.println();
        }
    }
    
    private static void solveDFS(int idx, LinkedList<Integer> resArr) {
        if(resArr.size() == SELECT) {
            for(int a : resArr) {
                System.out.print(a + " ");
            }
            System.out.println();
            return;
        }
        for(int i = idx; i < lottoArr.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                resArr.add(lottoArr[i]);
                solveDFS(i, resArr);
                resArr.removeLast();
                visited[i] = false;
            }
        }
    }
}
 

 

6. 결과

StringBuilder 사용

LinkedList 사용

확연한 차이가 보이시나요?

하나하나 뽑은걸 StringBuilder에 append시켜 결과값을 한 번에 출력시키는 것과

LinkedList에 add, remove하는 작업으로 6개를 뽑았을 때 결과를 그때 그때 출력하는 것의 차이 입니다.