(Java) 백준 15654번 - N과 M (5)

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

문제

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

N개의 자연수 중에서 M개를 고른 수열

접근

입력받은 N개의 수를 사용하여 가능한 수열조합을 모두 만든다. 재귀와 방문처리를 이용하는데 재귀를 통해 이번 재귀에서 사용한 수를 방문처리한다. 다음 재귀로 넘어가서 또 모든 수 중 방문처리가 안된 수를 사전순으로 사용한다. 다음 재귀에서도 방문처리 안된 수를 사용하는걸 반복한다. M개가 만들어지면 해당 수열을 출력하고 다른 수열을 만들기 위해 재귀를 깨고 돌아가면 방문처리를 다시 미방문으로 만들며 가능한 조합을 탐색한다.

문제해결

> 방문처리를 할 used boolean형 배열과, N개의 수를 담을 num배열, 결과 수열을 담을 result배열을 선언한다.
> 재귀로 수열을 만들 per메소드를 정의한다. 인자로는 수열의 수 rst를 받는다.
> 탈출 조건으로 수열의 크기인 rst가 M개면 result배열에 저장된 수열을 출력하고 깬다.
> 수열을 채우기 위해선 num배열에 있는 수를 꺼내 쓰는데 방문처리가 되어 있으면 그 수를 건너 뛰고 다른 수를 탐색한다.
> 수를 뽑았으면 그 수를 result배열에 넣고 방문처리를 해준 뒤 재귀로 다음 자리를 뽑으러간다.
> 재귀가 깨져 돌아오면 방문처리를 되돌려 주며 탐색을 이어나간다.
> main함수에선 N과 M을 입력받고 N개의 수를 입력받아 num을 만든다.
> 방문처리를 위해 수를 받으며 해당 수를 인덱스로 가지는 used배열도 초기값 true로 만들어준다.
> 사전순 처리를 위해 num배열을 정렬해주고 per메소드에 0을 넣어 호출한다.

코드

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

public class Main {
    //15654번 N과 M(5)
    static int N, M;
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static boolean[] used = new boolean[10001];
    static int[] num;
    static int[] result;
    static void per(int rst) {
        if(rst == M) {
            for(int i : result) sb.append(i).append(' ');
            sb.append('\n');
            return;
        }
        for(int i : num) {
            if(!used[i]) continue;;
            result[rst] = i;
            used[i] = false;
            per(rst+1);
            used[i] = true;
        }
    }
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        num = new int[N];
        result = new int[M];
        Arrays.fill(used, false);

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            int t = Integer.parseInt(st.nextToken());
            num[i] = t;
            used[t] = true;
        }
        Arrays.sort(num);

        per(0);
        System.out.print(sb);
    }
}

후기

방문처리를 이용해 접근하는데 boolean배열의 크기를 딱 num의 수 만큼만 하고싶었는데 일단 생각이 안나 하드코딩했다.
num배열을 어차피 수의 순서가 고정되어있으니 used도 N크기로 주고 num의 i번째에 접근할 때, used도 i번째로 접근해서 하면 되겠다고 생각했다.