[BOJ] 15654 - N과 M (5) (Java)

알고리즘

• 백트래킹

1. 문제

2. Idea

• dfs 수행 및 중복 조합 방지를 위한 방문 처리

3. 풀이

3.1. 변수 선언 및 초기화

• int N: 배열의 크기
• int M: 출력할 조합의 크기
• int[] arr: 입력된 숫자를 저장할 배열
• int[] answerArr: 조합을 저장할 배열
• boolean[] visited: 특정 요소가 사용되었는지 추적하기 위한 boolean 배열
• 입력 숫자 배열에 저장

        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());

        arr = new int[N];
        answerArr = new int[M];
        visited = new boolean[N];

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

3.2. 정렬 및 dfs 수행

• 깊이가 0인 상태에서 dfs(0) 호출로 시작

        Arrays.sort(arr); //입력된 숫자 오름차순 정렬
        dfs(0); //dfs 수행

3.3. dfs 함수

• 방문 여부를 추적하여 중복 조합 방지

    public static void dfs(int depth) {
        if (depth == M) { // depth가 M에 도달하면, 현재 answerArr 배열을 결과 문자열에 추가
            for (int val : answerArr) {
                sb.append(val).append(' '); // arr의 각 요소를 방문하여 조합을 생성
            } sb.append('\n'); return;
        }
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                answerArr[depth] = arr[i];
                dfs(depth + 1); //재귀 호출
                visited[i] = false; // 방문 여부 다시 false로 설정
            }
        }
    }

3.4. 결과 출력

        System.out.println(sb);

4. 전체코드

import java.io.*;
import java.util.*;
public class Main {
    public static int N, M;
    public static int[] arr;
    public static int[] answerArr;
    public static boolean[] visited;
    public static StringBuilder sb = new StringBuilder();


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

        // 1 ≤ M ≤ N ≤ 8
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());

        arr = new int[N];
        answerArr = new int[M];
        visited = new boolean[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr); //사전 순 정렬
        dfs(0); //dfs 수행
        System.out.println(sb);
    }

    public static void dfs(int depth) {
        if (depth == M) {
            for (int val : answerArr) {
                sb.append(val).append(' ');
            } sb.append('\n'); return;
        }
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                answerArr[depth] = arr[i];
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
}