[백준] N과 M (1) (15649번)

문제 이해

• 이 코드는 백트래킹(Backtracking) 알고리즘을 사용해 순열을 생성합니다.
• 주어진 n까지의 숫자 중에서 count개의 숫자를 선택해 가능한 모든 조합을 나열합니다.
• 방문 배열을 사용해 중복된 숫자 사용을 방지합니다.

 

핵심 아이디어

1. 백트래킹(Backtracking):
   • 각 숫자를 순차적으로 선택하면서 가능한 모든 경우를 탐색합니다.
   • 재귀를 사용해 숫자를 추가하고, 조건에 따라 추가했던 숫자를 제거하며 탐색을 진행합니다.
2. 방문 여부 체크:
   • 숫자가 이미 순열에 포함되었는지 확인하기 위해 boolean[] visit 배열을 사용합니다.
3. StringBuilder 사용:
   • 순열을 저장하고 출력하기 위해 StringBuilder를 사용합니다.
   • 매번 새로운 문자열을 생성하지 않고 효율적으로 문자열을 처리할 수 있습니다.
4. 백트래킹(Backtracking) 과정:
   • 재귀 호출 후에는 반드시 이전 상태로 돌아가기 위해 해당 숫자를 순열에서 제거하고 방문 여부를 초기화합니다.

 

알고리즘 흐름

1. 입력 받기: n과 count를 입력받아 사용할 숫자 범위와 순열 길이를 설정합니다.
2. 순열 생성 시작: recursion() 함수를 호출해 순열 생성을 시작합니다.
3. 순열 생성:
   • 숫자를 하나씩 선택해 순열을 확장합니다.
   • 모든 숫자를 다 사용한 경우 해당 순열을 출력합니다.
   • 이후 백트래킹을 통해 이전 상태로 복구하며 다른 경로를 탐색합니다.
4. 결과 출력: 가능한 모든 순열을 출력합니다.

 

추가 팁

• 조합(Combination)과의 차이:
  • 순열은 숫자의 순서가 중요하지만, 조합은 순서가 중요하지 않습니다.
  • 순열에서는 같은 숫자의 다른 순서도 다른 경우로 간주합니다.
• 시간 복잡도:
  • 이 알고리즘의 시간 복잡도는 O(n!)입니다. 숫자가 많아질수록 매우 많은 경우의 수를 탐색하므로, 숫자 범위가 커지면 주의해야 합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Main {

    static int n; // 사용할 숫자의 최대값 (1 ~ n)

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        n = in.nextInt(); // 사용할 숫자의 최대값 입력
        int count = in.nextInt(); // 순열에 포함될 숫자의 개수 입력

        boolean[] visit = new boolean[n + 1]; // 방문 여부를 체크하는 배열

        StringBuilder sb = new StringBuilder(); // 현재 순열을 저장할 StringBuilder 객체

        // 재귀 함수 호출: 방문 배열과 순열 길이, 문자열 저장 객체를 전달
        recursion(visit, count, sb);
    }

    
    public static void recursion(boolean[] visit, int count, StringBuilder sb) {
        // 순열의 길이를 모두 채웠을 경우 결과 출력
        if (count == 0) {
            System.out.println(sb.toString().trim()); // 순열 출력
            return; // 재귀 종료
        }

        // 1부터 n까지의 숫자를 순회하며 순열 생성
        for (int i = 1; i <= n; i++) {
            if (!visit[i]) { // 현재 숫자가 사용되지 않았으면
                visit[i] = true; // 해당 숫자를 사용으로 표시
                sb.append(i + " "); // 현재 숫자를 순열에 추가

                // 재귀 호출: 남은 숫자 개수를 줄이고, 현재 상태 전달
                recursion(visit, count - 1, sb);

                // 백트래킹: 순열에서 숫자를 제거하고, 방문 상태를 초기화
                sb.setLength(sb.length() - 2); // 마지막 숫자와 공백 제거
                visit[i] = false; // 방문 상태 초기화
            }
        }
    }
}