[백준] 6603번_로또_Java

접근

1. 입력

BufferedReader와 StringTokenizer를 사용하여 입력을, StringBuilder를 사용하여 출력을 수행한다

2. 백트래킹

• if(depth == m)
  depth가 m값인 6과 같다는 것은 로또 번호들이 모두 선택됐음을 의미함으로 nums 변수에 저장된 값을 모두 출력한다

• for(int i = 0; i < n; i++)
  depth가 m값보다 작은 경우에는 로또 번호 선택이 완료되지 않은 상태이기 때문에 for문을 통해 값을 채워나가도록 한다

  • if(!visited[i])
    visited 변수를 통해 이미 로또 번호로 포함된 숫자인지 확인한다
    visited[i]가 false일때 visited[i]를 true로 저장한 후 또 다른 if문을 선언한다

  • if(depth == 0 || (depth != 0 && lotto[depth - 1] < nums[i]))
    해당 if문은 로또 번호가 중복되지 않도록 한다
    숫자들을 오름차순으로 입력한다는 조건이 주어졌기 때문에 이미 로또 번호로 포함된 nums[i]값이 lotto[depth - 1] 의 값보다 커야 중복이 발생하지 않는다
    해당 조건을 만족하면 nums[i]값을 로또 번호에 포함시키고 depth를 1증가 시켜 dfs를 순환 호출한다

    함수가 return되면 visited[i]값을 false로 다시 저장한다
    

코드

package baekjoon.sort;

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

public class Main {
    private int n; // 선택할 숫자 개수
    private final int m = 6; // 로또 번호 개수
    private int[] nums; // 선택할 수 있는 로또 번호
    private int[] lotto; // 로또 당첨 번호
    private boolean[] visited;
    private StringBuilder sb = new StringBuilder();

	// 변수 초기화
    public Main(int n, int[] nums) {
        this.n = n;
        this.nums = nums;
        lotto = new int[m];
        visited = new boolean[n];
    }
	
    // 백트래킹 실행
    public void dfs(int depth) {
        if(depth == m) {
            for(int l : lotto) {
                sb.append(l + " ");
            }
            sb.append("\n");
            return;
        }
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;

                if(depth == 0 || (depth != 0 && lotto[depth - 1] < nums[i])) {
                    lotto[depth] = nums[i];
                    dfs(depth + 1);
                }
                visited[i] = false;
            }
        }
    }

	// 결과 출력
    public void printReulst() {
        System.out.println(sb);
    }

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

            int n = Integer.parseInt(st.nextToken());
            if(n == 0) break; // n의 값이 0일때 종료

            int[] nums = new int[n];
            for(int i = 0; i < n; i++) {
                nums[i] = Integer.parseInt(st.nextToken());
            }

            Main m = new Main(n, nums);
            m.dfs(0); // 백트래킹 실행
            m.printReulst(); // 결과 출력
        }
    }
}