[백준] 15649번 : N과 M (1) – JAVA [자바]

https://www.acmicpc.net/problem/15649

 

 

---

문제

 

 

---

해결 방법

이 문제는 백트래킹(Backtracking)을 활용하여 중복 없이 M개의 숫자를 선택하는 순열(Permutation) 문제이다. 다음과 같은 방식으로 해결할 수 있다.

1. 백트래킹을 이용한 순열 생성

• 1부터 N까지의 숫자 중에서 M개를 고른다.
• 숫자는 중복 없이 선택해야 한다.
• 사전 순으로 출력해야 하므로, 작은 숫자부터 선택한다.

 

2. 백트래킹을 수행하는 과정

• for 문을 이용해 1부터 N까지 순회하며 숫자를 선택한다.
• 이미 선택한 숫자는 방문 체크 배열(visited [])을 사용하여 중복을 방지한다.
• 선택한 숫자를 result [] 배열에 저장하고, 길이가 M이 되면 출력한다.
• 재귀 호출을 통해 다음 숫자를 선택하고, 선택이 끝나면 원상 복구(백트래킹)한다.

 

---

코드 

 

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

public class Main {
    static int n, m;
    static boolean[] visited;
    static int[] result; // 선택한 숫자를 저장하는 배열
    static StringBuilder sb; // 방문 여부 체크

    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());
        sb = new StringBuilder();

        visited = new boolean[n+1]; // 1~N 사용
        result = new int[m];
        backtrack(0);
        System.out.println(sb);
    }

    static void backtrack(int depth) {
        if (depth == m) { // M개를 선택했다면 출력
            for (int num : result) {
                sb.append(num).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {  // 아직 사용되지 않은 숫자라면 선택
                visited[i] = true;  // 방문 체크
                result[depth] = i;  // 선택한 숫자 저장
                backtrack(depth + 1);  // 다음 단계 진행
                visited[i] = false;  // 백트래킹 (원상복구)
            }
        }
    }
}

 

 

---

코드 설명

1. boolean [] visited를 이용해 중복 방지

• 숫자를 중복해서 선택하지 않도록 방문 여부를 visited [] 배열로 체크한다.

 

2. 백트래킹 (visited [i] = false)

• 한 번 선택한 숫자는 visited [i] = true로 설정해 중복을 방지한다.
• 재귀 호출이 끝난 후 visited [i] = false로 되돌려 다음 경우의 수를 탐색한다.

 

3. 사전 순 정렬 자동 보장

• for 문을 1부터 N까지 오름차순으로 순회하므로, 자동으로 사전 순으로 정렬된 결과가 출력된다.

 

백트래킹 흐름 예시

예제 입력: N = 3, M = 2

단계	result[] 상태	방문 체크 (visited [])	재귀 호출
1	[1, _]	[false, true, false, false]	backtrack(1) 호출
2	[1, 2]	[false, true, true, false]	출력: 1 2
3	[1, 3]	[false, true, false, true]	출력: 1 3
4	[2, _]	[false, false, true, false]	backtrack(1) 호출
5	[2, 1]	[false, true, true, false]	출력: 2 1
6	[2, 3]	[false, false, true, true]	출력: 2 3
7	[3, _]	[false, false, false, true]	backtrack(1) 호출
8	[3, 1]	[false, true, false, true]	출력: 3 1
9	[3, 2]	[false, false, true, true]	출력: 3 2

 

 

최종 출력

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

 

---

시간 복잡도 분석

1. 백트래킹 경우의 수

• N개의 숫자에서 M개를 선택하는 순열의 개수는 P(N, M) = N! / (N-M)!이다.
• 최댓값인 N = 8, M = 8일 때 P(8,8) = 8! = 40,320이므로 충분히 해결 가능하다.

 

2. 최악의 경우 시간 복잡도

• 백트래킹에서는 O(M!)의 시간 복잡도를 가진다.
• 하지만 M이 최대 8이므로 최대 40,320번 연산으로 충분히 빠르게 수행된다.

 

 

---

결론

• 백트래킹을 사용하여 중복 없이 M개의 숫자를 선택하는 순열(Permutation) 문제를 해결할 수 있다.
• boolean [] visited를 사용하여 중복을 방지한다.
• for 문을 이용해 1부터 선택하면 사전 순 정렬이 자동 보장된다.
• O(M!)의 복잡도를 가지지만 N, M이 작아 충분히 빠르게 실행된다.