[Java] 백준(실버-3) 15650번 - N과 M(2)

문제 풀이

---

이 문제는 앞서 풀었던 N과 M(1) 문제와 유사하게 백트래킹 기법을 이용하여 풀 수 있다.

아이디어 도출

문제를 살펴보면, N과 M을 입력받으면 1부터 N까지의 수 중 오름차순이면서 M의 길이까지 나열 가능한 수열이 되어야 한다. 예제 입력 3을 보면 알 수 있듯이 4 4 를 입력받을 경우, 오름차순 수열인 1 2 3 4 만 만족하는 것을 볼 수 있다.

그렇다면 재귀함수를 어떤식으로 구상해야 할까? 생각해낸 아이디어는 다음과 같다.

• 깊이를 의미하는 depth 변수뿐 아니라, 현재 위치를 의미하는 at 변수를 함께 사용한다.
  • at 변수는 재귀함수의 반복문에서 어디서부터 시작하는지를 결정해줄 변수가 된다.

    반복문에서 재귀함수를 호출할 때, at을 1부터 시작하도록 한다면 다음 재귀는 오름차순으로 탐색하기 위해 at에서 1이 증가된 2를 인자로 넘겨주며 다음 재귀에서는 반복문이 2부터 시작하게 된다.

• 이때, arr 배열에 i를 삽입한 후 다음 재귀에서는 at을 통해 i보다 1이 증가된 수부터 탐색하도록 하고, depth 또한 1 증가시킨 상태로 재귀호출을 해준다면 이전 값보다 큰 수부터 탐색하게 된다.

그리고 여기서는 재귀호출이 이루어지는 과정 안에서 배열의 모든 자리를 채우지 못한다면 깊이가 M과 같아질 수가 없기에 반복문이 먼저 끝나기 때문에 중복 방문 여부를 확인할 필요가 없다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;
import java.util.*;

class Main {    

    // 입력 N, M 선언
    static int N, M;
    
    // 수열을 담을 배열 선언
    static int[] arr;
    
    // 결과를 담아 출력할 StringBuiler 객체
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 수열을 담을 arr 배열 초기화
        arr = new int[M];

        // 재귀함수 호출
        DFS(1, 0);

        // 재귀함수에서 담아낸 수열 출력
        bw.write(sb+"\n");

        bw.close();
        br.close();
    }

    /**
     * 백트래킹 재귀함수
     * 시작할 현재 위치를 의미하는 at, 재귀의 깊이인 depth를 인자로 받는다.
     * idx가 M과 같다면 재귀를 종료한다.
     */
    static void DFS(int at, int depth) {
        // idx가 마지막 위치인 M이 된다면 수열을 출력하기 위해 재귀를 종료
        if(depth == M) {
            for(int num : arr) {
                sb.append(num).append(" ");
            }
            sb.append("\n");
            return;
        }
        // 오름차순인 수열을 구해야 하기에, at부터 N까지 탐색하며 현재 i값보다 다음 재귀에서 더 커야한다.
        for(int i=at; i<=N; i++) {
            // 현재 깊이인 depth을 인덱스로 하는 원소에 i값을 삽입
            arr[depth] = i;
            // // i+1의 값을 at으로 넘겨주며, depth 깊이도 1 증가시켜 재귀호출
            DFS(i + 1, depth + 1);
        }
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.