백준 15649(JAVA)

문제

풀이

재귀함수로 풀면된다.
재귀함수로 풀다가, 뽑고자하는 M개를 뽑으면 경우를 만들고, return해서 재귀 끝내주고 다시 그 다음 경우를 계속해서 보면된다.
수열은 중복이 되면 안된다는 것에 유의하자.

나는 두가지 방법으로 풀었다.

1) stack을 이용한 풀이

방문한 숫자의 순서를 기록해야 하므로 먼저 방문한 녀석을 순서대로 스택에 담는 형태로 풀었다.

방문한 숫자를 스택에 넣고,
스택의 크기가 M과 같으면 stack에 들어간 순서대로 출력하고,
다시 스택에서 빼고..
(스택에 해당 수가 있으면 다음 숫자 탐색)

를 반복해서 풀었따.

2) visited boolean 배열과, 결과를 담을 result int 배열

중복에 대한 처리는 visited boolean 배열을 통해 하였다.
그리고 탐색한 수의 순서는 result배열을 이용함.

코드

• stack

package training.backtracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

//== 1 ~ N 수중 중복없이 M개 모두 출력 - (사전 순) ==//
public class Main15649 {
    static int N, M;
    static Stack<Integer> stack = new Stack<>();

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

        recursive(0);

    }
    static void recursive(int V){
        if(V == M){
            StringBuilder sb = new StringBuilder();
            for (Integer integer : stack) {
                sb.append(integer + 1 + " ");
            }
            System.out.println(sb);
            return;
        }

        for(int i = 0; i < N; i++){
            if(!stack.contains(i)){
                stack.push(i);
                recursive(V + 1);
                stack.pop();
            }
        }
    }
}

• visited, result

package training.backtracking;

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

//== 1 ~ N중 중복없이 M개 뽑기 =//
public class Main15649_2 {
    static int N, M;
    static boolean[] visited;
    static int[] result;

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

        visited = new boolean[N];
        result = new int[M];

        recursive(0);
    }
    static void recursive(int m){
        if(m == M){
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < M; i++){
                sb.append(result[i] + " ");
            }
            System.out.println(sb);
            return;
        }

        for(int i = 0; i < N; i++){
            if(!visited[i]){
                visited[i] = true;
                result[m] = i + 1;
                recursive(m + 1);
                visited[i] = false;
            }
        }
    }
}