[백준] 6603번 로또 - Java, 자바

난이도

실버 2

문제

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

풀이

백트래킹

주어진 수에서 6개의 수를 골라야한다.
단, 여기서 숫자는 중복될 수 없고 순열이 아닌 조합이다. (로또의 순서가 의미가 없다)

백트래킹을 수행한다.
1) 종료조건 depth 가 6일 때, 로또 저장한 배열을 출력한다.
2) 종료조건이 아닐 때,
visit 배열을 사용해서 중복된 수가 들어오지 못하도록 한다.
for문에 초기값을 i=start로 해서, 순열이 아닌 조합을 만들도록 한다.

    static void back(int start, int depth) {
        if (depth == 6) {
            for (int val : result) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = start; i < n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                result[depth] = arr[i];
                back(i, depth + 1);
                visit[i] = false;
            }
        }
    }

코드

package 백트래킹;

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

public class BOJ6603 {
    static int n;
    static int[] arr;
    static boolean[] visit;
    static int[] result;
    static StringBuilder sb = new StringBuilder();

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

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            n = Integer.parseInt(st.nextToken());
            if (n == 0)
                break;

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

            result = new int[6];
            visit = new boolean[n];
            back(0, 0);

            System.out.println(sb);

        }

    }

    static void back(int start, int depth) {
        if (depth == 6) {
            for (int val : result) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = start; i < n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                result[depth] = arr[i];
                back(i, depth + 1);
                visit[i] = false;
            }
        }
    }
}