[백준] 15649 : N과 M(1) - Java

• 백준 문제 URL

N과 M (1)은 기본적인 백트래킹(permutation) 문제로,
1부터 N까지의 숫자 중에서 중복 없이 M개를 선택해 나열하는 모든 경우의 수를 출력해야함

---

문제 접근

• 입력: N, M
• 출력: 1부터 N까지 중 M개의 수를 고른 모든 순열
• 핵심 개념:
  1. DFS(Depth-First Search) 방식의 백트래킹
  2. 중복 제거용 visited 배열(여기서는 checked)

모든 수를 순서대로 탐색하면서, 아직 방문하지 않은 숫자를 하나씩 선택해 리스트에 추가함.
리스트의 크기가 M이 되면 이를 하나의 결과로 저장하고 재귀를 종료함.

---

제출

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

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

        List<Integer> inputList = new ArrayList<>();
        for (int i = 1; i <= n; i++) inputList.add(i);

        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> numList = new ArrayList<>();
        boolean[] checked = new boolean[inputList.size()];

        function(m, inputList, temp, numList, checked);

        for (List<Integer> a : numList) {
            StringBuilder sb = new StringBuilder();
            for (int i : a) sb.append(i).append(' ');
            System.out.println(sb);
        }
    }

    public static void function(int m, List<Integer> inputList, List<Integer> temp,
                                List<List<Integer>> numList, boolean[] checked) {
        if (temp.size() == m) {
            numList.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < inputList.size(); i++) {
            if (checked[i]) continue;
            temp.add(inputList.get(i));
            checked[i] = true;

            function(m, inputList, temp, numList, checked);

            temp.remove(temp.size() - 1);
            checked[i] = false;
        }
    }
}

---

핵심 포인트

• temp는 현재까지 선택된 숫자를 저장함.
• checked[i]는 inputList[i] 사용 여부를 추적함.
• numList에는 완성된 한 경우의 순열을 추가함.
• 재귀 호출이 끝날 때마다 마지막 요소를 제거하여 백트래킹 수행함.

---

출력 예시

입력

3 2

출력

1 2
1 3
2 1
2 3
3 1
3 2

---

정리

• 기본적인 순열(백트래킹) 예제 코드
• 시간 복잡도는 $O(N!)$ 수준으로, N이 커질수록 조합의 수가 급격히 늘어남.
• DFS와 백트래킹 구조를 이해하기 위한 입문 문제로 적합