백준 15650번, N과 M (2) (with.Java)

백준 15650번, N과 M (2) (with.Java)에 대하여 알아본 글입니다.

코딩 테스트 문제를 풀며, 풀었던 문제에 대한 회고와 다른 풀이 방법을 알아보며, 알아가고자 합니다.

문제에 대해 먼저 알아보겠습니다.

문제

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

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다.

입력

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

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.

중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

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

문제 풀이

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

class Main {
    public static int[] arr;
    public static int N, M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.valueOf(st.nextToken());
        M = Integer.valueOf(st.nextToken());
        arr = new int[M];

        dfs(1, 0);
    }

    public static void dfs(int el, int depth){
        if(depth == M){
            for(int i : arr){
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        for(int i = el; i <= N; i++){
            arr[depth] = i;
            dfs(i + 1, depth + 1);
        }
    }
}

풀이 설명

이 코드는 조합(combination)을 구하는 문제를 해결하는 프로그램입니다.

주어진 N개의 숫자 중에서 M개의 숫자를 선택하여 가능한 모든 조합을 출력합니다.

이를 재귀적인 깊이 우선 탐색(DFS, Depth-First Search) 방법을 사용하여 구현합니다.

입력 처리: 프로그램은 BufferedReader를 통해 N과 M 값을 입력받습니다.

N은 사용할 숫자의 범위를, M은 선택할 숫자의 개수를 나타냅니다.

이때, M 크기의 배열 arr을 생성하여 선택된 숫자들을 저장합니다.

재귀 호출을 통한 조합 생성: 프로그램은 dfs라는 재귀 함수를 호출하여 조합을 생성합니다.

dfs 함수는 현재의 숫자(el)와 깊이(depth)를 인자로 받습니다.

기저 조건: depth가 M에 도달하면, arr 배열에 저장된 M개의 숫자를 출력합니다.

재귀 호출: for문을 통해 현재 숫자 i부터 N까지 반복하며, arr[depth]에 현재 숫자를 저장하고, 다음 깊이에서 dfs를 호출합니다.

이때, 다음 숫자로 i + 1을 넘겨줌으로써 숫자가 중복되지 않도록 보장합니다.

출력: 조합이 완성되면, arr 배열에 저장된 값을 출력합니다.

이제, dfs(i + 1, depth + 1) 대신 dfs(el + 1, depth + 1)을 사용했을 경우의 결과와 그 이유를 설명하겠습니다.

현재 코드(dfs(i + 1, depth + 1)): 이 코드는 현재 숫자 i를 기준으로 다음 숫자를 탐색합니다.

예를 들어, i가 1일 때 다음 재귀 호출에서는 i + 1, 즉 2부터 탐색을 시작하게 됩니다.

이 방식은 중복 없이 올바른 조합을 만들어냅니다.

잘못된 코드(dfs(el + 1, depth + 1)): 만약 i + 1 대신 el + 1을 사용하게 되면, 재귀 호출 시마다 초기 숫자인 el의 다음 숫자를 탐색하게 됩니다.

이로 인해, 모든 재귀 호출이 동일한 el을 기준으로 진행되어 중복된 숫자가 선택되거나, 올바른 조합을 생성하지 못하게 됩니다.

예를 들어, 처음 el이 1이라면 모든 재귀 호출에서 el이 1에 고정되어 잘못된 조합을 생성하게 됩니다.

결론적으로, 조합을 구하기 위해서는 현재의 숫자 i를 기준으로 다음 숫자 i + 1부터 탐색해야 하며, el + 1을 사용하면 재귀 호출이 올바르게 진행되지 않습니다.