백준 코딩 15649 : 백트래킹(N과 M 1)

문제

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

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

입력

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

출력

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

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

 

15651번(N과 M 3)과 다른 점은 중복되는 수열을 여러 번 출력하면 안된다는 것이다.

따라서 재귀함수에서 Stack을 활용해 검사 대상 값을 먼저 Stack에 넣어 놓은 뒤 그 다음에 출력 될 숫자가 Stack에 있는 값인 경우 해당 재귀함수를 수행하지 않도록 설정한다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static int N = 0;
    static int M = 0;
    static StringBuilder stb = new StringBuilder();
    static Stack<Integer> stack = new Stack<Integer>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str);
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        rec(0,"");
        System.out.println(stb.toString());
 
    }
 
    public static void rec (int now, String inputNum) {
        if (now == M) {
            stb.append(inputNum.trim()+"\n");
        } else {
            now++;
            for (int i = 1 ; i <= N; i++) {
                if (!stack.contains(i)) { 
                    stack.push(i);               
                    rec(now, inputNum+" "+i);                                     
                    stack.pop();
                } 
 
            }
        }
 
    }
}

15651번과 비교했을 때 이번 문제는 다음의 내용이 추가 되었다.

 

1. 스택 선언

static Stack<Integer> stack = new Stack<Integer>();

 

2. 수열 중복값 검사

if (!stack.contains(i)) {        

                    stack.push(i);               

                    rec(now, inputNum+" "+i);                                               

                    stack.pop();

                } 

 

처음 수열 값이 1이라고 가정하면 재귀함수에서 for문 i값이 1부터 시작하므로 if (!stack.contains(i)) 에서 스택이 '1'이라는 값을 포함하고 있는지 없는지 검사한다. 

만약 없다면 스택에 해당 값 1을 넣어놓고 다음 재귀함수로 들어가(now값 +1 증가) 두번째로 출력될 수열의 값이 1과 같은지 if (!stack.contains(i))를 통해 다시 검사를 한다. 출력 내용 '1 1'은 스택에 있는 값 1과 두번째 수열의 값 1이 같으므로 for문 안의 if문의 조건에 걸리지 않게 되어 바로 빠져나가 최종적으로 출력이 되지 않는다.

첫번째 숫자 1에 대한 모든 중복검사가 끝이 나면 stack.pop(); 을 통해 스택에 들어 있던 1을 빼내고 다음 for 조건식으로 들어가 stack에 2를 넣게 된다.

 

입력예시 : 4 2

 

rec(0," ") 메소드를 실행시켰을 때 나오는 과정은 다음과 같다.

 

rec(0,"") = rec(1,"1") + rec(1,"2") + rec(1,"3") + rec(1,"4")
           = rec(2,"1"+"1") + rec(2,"1"+"2") + rec(2,"1"+"3") + rec(2,"1"+"4")
              + rec(2,"2"+"1") + rec(2,"2"+"2") + rec(2,"2"+"3") + rec(2,"2"+"4")
              + rec(2,"3"+"1") + rec(2,"3"+"2") + rec(2,"3"+"3") + rec(2,"3"+"4")
              + rec(2,"4"+"1") + rec(2,"4"+"2") + rec(2,"4"+"3") + rec(2,"4"+"4")

           =   "1 1 \n" + "1 2 \n" + "1 3 \n" + "1 4 \n"  

               + "2 1 \n" + "2 2 \n" + "2 3 \n" + "2 4 \n"

               + "3 1 \n" + "3 2 \n" + "3 3 \n" + "3 4 \n" 

              + "4 1 \n" + "4 2 \n" + "4 3 \n" + "4 4 \n" 

 

출력 결과