[BOJ] 15649번 : N과 M (1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 시간 제한 : 1초
- 메모리 제한 : 512MB

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

접근 방법

해당 문제는 15651번 문제와 유사합니다. 차이점은 자연수를 중복하여 선택할 수 없다는 점입니다. 예를 들어 1 1 2와 같은 경우 첫째 자리와 둘째 자리에 1이 중복으로 존재하므로 해당 수열은 생성할 수 없습니다. 알맞은 수열만 생성하기 위해 자연수가 이미 선택되어 사용할 수 없는지 상태를 저장할 배열이 필요합니다.

// rec번째 자리의 수를 결정할 함수
static void func(int rec) {
	// 모든 자리의 수를 결정한 경우
    if (rec == m) {
    	// StringBuilder를 이용하여 해당 수열을 저장
        for (int i : selected) {
            sb.append(i).append(" ");
        }

        sb.append('\n');
        return;
    }

	// 아직 모든 자리의 수를 결정하지 않은 경우
	// 1부터 n까지의 자연수 중에서 선택
    for (int i = 1; i <= n; ++i) {
    	// 자연수 i가 아직 선택되지 않은 경우
        if (!unavailable[i - 1]) {
            unavailable[i - 1] = true; // 선택된 상태를 저장하여 다른 자리에서 선택이 되지 않도록 함
            selected[rec] = i; // rec번째 자리의 수는 i

            func(rec + 1); // 다음 자리의 수를 재귀를 이용하여 결정

            unavailable[i - 1] = false; // 다른 수열을 생성하기 위해 선택된 상태 해제
        }
    }
}

15651번과 차이점은 자연수가 다른 자리에서 선택이 되었는지 if문과 boolean 배열을 이용하여 확인 후 아직 선택이 되지 않은 경우에만 해당 자연수를 선택합니다. 자연수를 선택을 하면 다른 자리에서 같은 자연수를 선택하면 안되므로 선택된 상태를 boolean 배열에 저장하여 재귀 함수를 호출하는 것을 볼 수 있습니다. 수열 생성이 끝난 뒤에는 자연수가 선택된 상태를 해제하여 다음 수열 생성시 올바르게 생성되도록 하였습니다.

코드

import java.util.Scanner;

class Main {

    private static int n;
    private static int m;
    private static boolean[] unavailable;
    private static int[] selected;
    private static final StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        input();
        func(0);
        System.out.println(sb);
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        selected = new int[m];
        unavailable = new boolean[n];

        sc.close();
    }

    static void func(int rec) {
        if (rec == m) {
            for (int i : selected) {
                sb.append(i).append(" ");
            }

            sb.append('\n');
            return;
        }

        for (int i = 1; i <= n; ++i) {
            if (!unavailable[i - 1]) {
                unavailable[i - 1] = true;
                selected[rec] = i;

                func(rec + 1);

                unavailable[i - 1] = false;
            }
        }
    }
}

주의할 점

수열을 생성한 뒤 반드시 사용된 자연수들의 선택을 해제해주어야 합니다. 그렇지 않으면 다음 수열 생성시 수열이 제대로 생성이 되지 않습니다.
자연수가 선택 가능한지 저장하는 것이 아니라 자연수가 이미 선택되었는지 저장하는 것이 더 좋습니다. 그 이유는 멤버 변수와 클래스 변수의 boolean은 기본적으로 false 값을 가지기 때문입니다. 선택 가능성을 저장할 경우 초기에 boolean 배열을 생성시 true로 초기화 하여야하는데 이는 O(N)의 시간이 걸리는 작업입니다. 해당 문제의 경우 N이 8이하의 값을 가지므로 문제가 되지 않지만 N이 충분히 큰 경우에는 이를 고려해야할 것입니다.