백준 15651번, N과 M (3) (with.Java)

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

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

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

문제

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

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

문제 풀이

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

class Main{
    public static int N, M;
    public static int[] arr;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        br.close();


        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[M];

        dfs(0);

        bw.flush();
        bw.close();
    }

    public static void dfs(int depth) throws Exception{
        if(depth == M){
            for (int i = 0; i < M; i++){
                bw.write(arr[i] + " ");
            }
            bw.write("\n");
            return;
        }

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

풀이 설명

이 코드는 백트래킹을 활용하여 1부터 N까지의 숫자로 구성된 M개의 순열을 생성하고 출력하는 프로그램입니다.

먼저, BufferedReader를 사용하여 입력을 받고, StringTokenizer를 활용하여 공백으로 구분된 두 개의 정수 N과 M을 파싱합니다.

N은 선택할 수 있는 숫자의 범위를 나타내며, M은 출력할 순열의 길이를 의미합니다.

입력을 처리한 후 BufferedReader를 닫습니다.

배열 arr은 크기가 M인 정수 배열로, 현재 구성 중인 순열을 저장하는 역할을 합니다.

이후 dfs(0)을 호출하여 깊이 우선 탐색(DFS)을 시작합니다.

dfs 메서드는 백트래킹을 수행하는 재귀 함수입니다. 이 함수는 현재 depth 값을 인자로 받으며, depth가 M과 같아지면 arr에 저장된 값을 BufferedWriter를 사용하여 출력합니다.

이때, 각 숫자는 공백으로 구분되며, 순열이 완성될 때마다 개행 문자를 추가합니다.

반복문을 통해 1부터 N까지의 숫자를 순차적으로 선택하며 arr[depth]에 저장한 뒤, dfs(depth + 1)을 호출하여 다음 깊이로 이동합니다.

이렇게 하면 중복을 허용하는 모든 경우의 수를 탐색하게 됩니다.

모든 DFS 호출이 종료된 후 BufferedWriter의 버퍼를 비우고 닫아 출력 작업을 마무리합니다.

이를 통해 중복된 숫자를 허용하는 길이 M의 모든 순열을 효율적으로 생성하고 출력할 수 있습니다.