[백준 / Java] 15651번 N과 M (3)

사용한 알고리즘(백트래킹)

https://cobi-98.tistory.com/22

[필수 알고리즘] 재귀호출 기본 -백트래킹(Backtracking)

 

🔒 15651번 N과 M (3)

✔ 문제 설명

🚩 요구사항 분석

• 1부터 N까지 자연수 중에서 M개를 고른 수열
•  중복해서 조합 할 수 있다.

 

🔑 문제풀이

자연수 N과 M을 정의하기위해 BufferedReader 을 사용하여 StringTokenizer로 값을 전역변수 지정하였다.

 

중복을 허용하기에  boolean으로 방문 기록을 담을 필요없이 depth를 통해 재귀가 깊어질 때마다  (DMBackTracking함수) depth를 1씩 증가시킨다.

더이상 탐색할 자식 노드가 없다면(M과 같아지면) 더이상 재귀를 호출하지 않고 탐색과정 중 값을 담았던 arr 배열을 출력해주고 return 해준다.

 

다음과 같이 출력이 많은 String 의 경우 StringBuilder을 사용하여 효율성을 높이는 것을 활용하였다.

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

public class Main{

    public static int N;
    public static int M;
    public static int [] arr;
    public static StringBuilder sb = new StringBuilder();

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

        arr = new int[M];

        NMBacktracking3(0);
        System.out.println(sb);
    }

    public static void NMBacktracking3(int depth){
        if(depth == M){
            for (int value : arr) {

                sb.append(value).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = 0; i < N; i++) {
                arr[depth] = i+1;
                NMBacktracking3(depth+1);
        }
    }
}