[BOJ] 15650 - N과 M (2) (Java)

알고리즘

• 백트래킹

1. 문제

2. Idea

• dfs와 백트래킹 모두 사용
  • DFS: 탐색을 진행하면서 가능한 경로를 탐색
  • 백트래킹: 선택한 숫자가 이후의 선택에 영향을 주는 경우
    • 한 번 선택한 숫자는 다음에 선택할 수 없도록 제한하고, 이를 표시하기 위해 visit 배열을 사용

3. 풀이

3.1. 변수 선언 및 초기화

• n: 전체 숫자의 개수
• m: 선택할 숫자의 개수
• visit: 각 숫자의 방문 여부를 나타내는 boolean 배열
• arr: 선택된 숫자들을 저장하는 배열
  • 조합을 만들 때마다 해당 배열에 선택된 숫자들을 저장

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        visit = new boolean[n];
        arr = new int[m];

3.2. dfs 함수 호출 및 조합 생성

• dfs(0, 0)를 호출
• 깊이 depth는 0부터 시작하고, 다음에 선택할 숫자의 시작 위치 start도 0부터 시작
• dfs에서는 현재까지 선택한 숫자의 개수가 m과 같아지면 선택한 숫자들을 출력하고 종료한다.
  • 그렇지 않으면 가능한 숫자를 선택하고 다음 단계로 재귀 호출하는 방식으로 진행

	dfs(0,0);
    ...
    
    private static void dfs(int depth, int start) {
        if (depth == m) {
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

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

3.3. 결과 출력

• 모든 조합을 생성하고 출력

		System.out.println(sb);

4. 전체코드

import java.io.*;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int n, m;
    static boolean[] visit;
    static int[] arr;


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

        visit = new boolean[n];
        arr = new int[m];
        dfs(0,0);
        System.out.println(sb);
    }

    private static void dfs(int depth, int start) {
        if (depth == m) {
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

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