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

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

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

예제 입력 1 복사

3 1

예제 출력 1 복사

1
2
3

예제 입력 2 복사

4 2

예제 출력 2 복사

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

예제 입력 3 복사

4 4

예제 출력 3 복사

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

나의 풀이

백트래킹문제로 m을 count로 두고 m번만큼 재귀함수를 실행하면서 답을 찾아낸다. 또한 중복이 없어야 하므로 방문했던 것에는 visit배열에서 boolean값으로 처리해주면 되며 중요한 점은 다시 백으로 돌아갈때 visit을 false로 되돌려주는 것이다.

코드

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

/**
 * 15649번 N과 M (1)
 */
public class Baeckjun15649 {
    static int n,m;
    static StringBuffer sb = new StringBuffer();        // 가능한 모든 수열을 저장하는 버퍼
    static boolean[] visit;                // 방문여부 함수
    static char[] seq;                        // 가능한 수열을 담는 배열    

    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());

        visit = new boolean[n+1];
        seq = new char[m*2];                    // 공백을 담기위해 m의 2배만큼 할당한다.
        Arrays.fill(seq, ' ');                // 공백으로 초기화.

        back(0);
        System.out.println(sb.toString());

    }

    static void back(int count) {
        if (count == m) {
            sb.append(seq);
            sb.append("\n");
            return ;
        }

        for (int i=1; i<=n; i++) {
            if (visit[i]) continue;

            visit[i] = true;
            seq[count*2] = (char)(i+'0');        // integer를 '0'에서 i만큼 더해주면 숫자인 문자가 된다.
            back(count+1);
            visit[i] = false;                    // 뒤로 백하는거니까 다시 false로 되돌려줘야한다!!
        }
    }
}