[BOJ/Java] 15649. N과 M (1)

[BOJ/Java] 15649. N과 M (1)

16918번: 봄버맨

---

풀이

package edu.ssafy.im.BOJ.No15649;

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

public class Main {
    int[] arr; // 주어진 자연수 배열
    int[] sel; // 선택한 숫자들을 담을 배열
    boolean[] visited; // 방문 여부를 체크할 배열
    StringBuilder sb = new StringBuilder(); // 결과를 담을 StringBuilder

    public static void main(String[] args) throws IOException {
        new Main().sol();
    }

    private void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력 처리
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);

        int n = Integer.parseInt(st.nextToken()); // 주어진 자연수의 개수
        int m = Integer.parseInt(st.nextToken()); // 선택할 숫자의 개수

        arr = new int[n]; // 주어진 자연수 배열 초기화
        sel = new int[m]; // 선택한 숫자 배열 초기화
        visited = new boolean[n]; // 방문 여부 배열 초기화

        // 주어진 자연수 배열 초기화
        for (int i = 1; i <= arr.length; i++) {
            arr[i - 1] = i;
        }

        recursive(0); // 재귀 함수 호출하여 수열 생성
        System.out.print(sb); // 결과 출력
    }

    private void recursive(int m) {
        // 기본 파트: 선택할 숫자의 개수만큼 숫자를 선택한 경우
        if (m == sel.length) {
            for (int s : sel)
                sb.append(s).append(" "); // 선택한 숫자들을 StringBuilder에 추가
            sb.append("\n"); // 줄바꿈
            return;
        }

        // 재귀 파트
        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) { // 아직 방문하지 않은 숫자인 경우
                visited[i] = true; // 방문 표시
                sel[m] = arr[i]; // 선택한 숫자 배열에 추가
                recursive(m + 1); // 다음 위치로 이동하여 재귀 호출
                visited[i] = false; // 방문 표시 해제 (백트래킹)
            }
        }
    }
}