[백준15649] N과 M (1) / Java

TITLE

문제주소 : www.acmicpc.net/status?from_problem=1&problem_id=15649

 

---

<문제 설명>

문제

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

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

입력

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

출력

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

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

 

<풀이법>

▒ 한줄 개념: 재귀 DFS(백트래킹) + 올바른 Parameter ▒

백트래킹 알고리즘을 사용하는 가장 기초적인 문제입니다.

재귀형 DFS 알고리즘에서는 가장 중요한 것이 Parameter와 Return인데, 출력이 목적이므로 Return값은 따로 사용하지 않고 Parameter만을 사용하여 재귀를 구현하였습니다.

 

우선 입력된 N 만큼의 스택을 생성합니다. 배열이 아닌 스택을 이용하는 이유는, 재귀함수의 Parameter로 현재 뽑아낸 원소 외의 나머지 배열을 넘겨줄건데, 스택을 이용하는 것이 특정 인덱스의 원소를 뽑아내기 쉽기 때문입니다.(Stack.remove()). 그 후 재귀함수 search는 넘겨받은 스택에서 하나의 원소를 또 뽑아내고, 그 나머지 스택을 다시한번 search()에 Parameter로 넘겨줍니다.

 

이번 코드의 핵심 함수인 search의 parameter는 다음과 같습니다. 

• int M : 몇개까지 출력할 건지 입력된 값
• int cur : 현재 뽑아내져 있는 값
• Stack stack : 기존 스택에서 cur가 뽑혀나오고 나머지 스택
• String string : 나중에 출력하기 위해 원소 값을 쌓아나가는 String

 

<코드(Java)>

package Baekjoon;

import java.util.Scanner;
import java.util.Stack;

public class N_and_M_15649 {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        Stack<Integer> stack = new Stack<>();

        for(int n = 0 ; n < N; n++){
            stack.add(n+1);
        }

        for(int i = 0; i<N; i++){
            Stack<Integer> temp = (Stack<Integer>)stack.clone();
            search(M, temp.remove(i), temp, "");
        }
    }

    static void search(int M, int cur, Stack<Integer> stack, String string){
        string += cur;
        if(string.length() == M*2 - 1 ){
            System.out.println(string);
        }
        else{
            int size = stack.size();
            for(int i = 0; i < size; i++){
                Stack<Integer> temp = (Stack<Integer>)stack.clone();
                search(M, temp.remove(i), temp, string+" ");
            }
        }
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest