백준 코딩 15652 : 백트래킹 (N과 M 4)

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

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

출력

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

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

 

 

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++) {
                stack.push(i);
                if (stack.size() >= 2) {
                    int first = stack.get(now - 2);
                    int second = stack.get(now - 1);
                    if (second >= first) {
                        rec(now, inputNum+" "+i);
                        stack.pop();
                    } else {
                        stack.pop();
                    }
                } else {
                rec(now, inputNum+" "+i);
                stack.pop();
                }
            } 
 
        }
    }
}

우선 이전 N과M 문제와 마찬가지로 모든 경우의 수를 탐색하기 위한 Stack 클래스를 선언한다. 

이 문제의 출력방식은 비내림차순 수열이기 때문에 백트래킹 알고리즘의 유망성 판단 조건으로 수열의 현재값이 이전값보다 같거나 큰가? 로 설정하여 유망성 조건을 만족하지 못하면 이전 부모 노드로 돌아가 다음 자식 노드를 탐색하도록 구현한다.

 

 

 

위 그림은 유망성 판단 조건 및 중복 여부 검사를 하지 않고 모든 경우의 수를 고려한 트리를 나타낸 그림이다.

(예시 입력 3 3)

트리 작성 : http://mshang.ca/syntree/

 

첫 for문이 시작되면 stack.push(i); 를 통해 Stack에 i = 1 값을 넣는다. 유망성 판단 조건이 두 값의 비교이기 때문에 스택의 크기가 1일 경우 비교대상이 없으므로 rec(now, inputNum+" "+i); 로 바로 재귀 메소드를 실행한다.

재귀 메소드가 실행되면서 스택에 다음 값을 바로 넣기 때문에 스택의 크기는 2가 된다.

 

(stack.size() >= 2)의 조건을 만족하므로 수열 이전의 값을 int first = stack.get(now -2); 수열 현재의 값을 int second = stack.get(now - 1); 로 초기화한다.

 

이후 두 값을 비교하여 second값이 first값보다 크거나 같다면(유망성 판단조건) 다음 노드 탐색을 위해

재귀 메소드를 다시 수행한다. 재귀 메소드가 종료되면stack.pop(); 을 통해 스택에 있던 값을 빼내고 이전 부모노드로 돌아간다.

 

유망성 판단조건을 만족하지 못한다면 스택에 있던 값을 빼내고 이전 부모노드로 바로 돌아간다.

 

유망성 조건을 판단하여 최적 루트를 찾아가는 예시를 하나 들어보자.

 

 

 

1. 처음 STACK에 2가 들어가고 재귀 메소드를 실행.

2. 재귀 메소드 안의 for 반복문에 의해 1이 STACK에 추가로 들어간다.

3. 처음 들어간 2가 first값이 되고 나중에 들어간 1이 second 값이 된다.

 

 

 

 

유망성 판단조건(if (second >= first))을 만족하지 못하므로  stack.pop(); 을 실행하여 1을 빼내고 다음 반복문을 실행시켜 이전 부모 노드로 돌아간다.

 

 

 

 

다음으로 스택에 2가 들어가고 first와 second값이 같으므로 유망성 판단조건을 만족한다. 이후 다음 자식노드로 들어가 1부터 다시 탐색을 하게 되며 다시 한번 유망성 판단을 통해 2보다 같거나 큰 값을 스택에 추가시킨다. 예시로 3 3 을 입력했기 때문에 깊이가 3이되는 순간 재귀 메소드가 종료되므로 스택에 있던 값을 차례대로 StringBuilder에 넣어놓은 뒤 스택에 있던 모든 값을 빼낸다.

 

모든 반복문이 끝나면 StringBuilder에 있던 모든 문자열을 toString 메소드를 통해 출력시킨다.

 

 출력 결과