• 문제: https://www.acmicpc.net/problem/6603

설명

이번 문제는 백트래킹 방식이 아직 익숙하지 않아 코드로 구현하는데 어려움이 있었다.

입력

• K개의 수가 오름차순으로 정렬되어 들어온다.
• K개의 수를 방문 표시하기 위한 boolean[] visited 배열을 생성한다.
• 입력받는 숫자들을 담을 int[] numbers 배열을 생성한다.

탐색
6자리의 로또를 출력하기 위해 탐색한다.

• 로또 개수(6개)만큼 세팅될 때까지 재귀 호출을 반복한다.
  • 수의 선택이 끝나면 다시 해당 수를 방문하지 않았다고 false로 지정한다.
  • 초기값을 start로 하여, 순열이 아닌 조합을 만든다.

출력

• visited 배열에서 방문한 곳들을 확인하고, 방문했다면 방문한 곳의 index를 가지고 numbers 배열에서 출력한다.
  • 이미 수는 정렬되었으므로 사전 순으로 가장 먼저 오는 순서가 출력된다.

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class P6603 {
    static Integer n;
    static StringBuilder sb;
    static boolean[] visited;
    static int[] numbers;

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

        while (true) {
            String testCase = br.readLine();
            if (testCase.equals("0")) {
                break;
            }
            st = new StringTokenizer(testCase);
            n = Integer.parseInt(st.nextToken());
            visited = new boolean[n];
            numbers = new int[n];

            for (int i = 0; i < n; i++) {
                numbers[i] = Integer.parseInt(st.nextToken());
            }
            DFS(0, 0);
            sb.append("\n");
        }
        System.out.println(sb);
    }

    private static void DFS(int start, int depth) {
        if (depth == 6) {
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    sb.append(numbers[i]).append(" ");
                }
            }
            sb.append("\n");
        }

        for (int i = start; i < n; i++) {
        // 조합이기 때문에 start를 이용해서 이미 확인한 부분은 넘어간다.
            if (!visited[i]) {
                visited[i] = true;
                DFS(i + 1, depth + 1);
                visited[i] = false;
            }
        }
    }
}

Reference

• https://roomconerdeveloper.tistory.com/66
• https://sdesigner.tistory.com/56