[백준(Baekjoon)] 15651. N과 M (3) (java, DFS/백트래킹)

안녕하세요. 이번에는 백준 15651. N과 M (3) 문제를 풀어보겠습니다.

문제 링크

https://www.acmicpc.net/problem/15651

문제 풀이

✔ 입출력 및 요구사항 확인

1부터 N까지 자연수 중에서 M개를 골라야 하며, 같은 수를 여러 번 골라도 됩니다.

✔ "같은 수를 여러 번 골라도 된다" 의 의미

같은 수를 여러 번 고르기 위해서는 모든 경우를 탐색해야 합니다. 그렇기 때문에 이전 N과 M (1) 문제나 N과 M (2) 문제와는 달리 visited 배열로 방문여부를 체크해 줄 필요가 없습니다.

핵심 로직은 다음과 같습니다.

int[] answer = new int [m];

//n = 탐색해야 할 자연수(1부터 n까지)
//m = 골라야 하는 숫자의 갯수
//idx = 현재까지 dfs함수를 탐색하면서 골라둔 숫자의 갯수
dfs(int n, int m, int idx) {
    //dfs 탐색을 멈추는 로직
    if(idx가 m과 같다면) {	//dfs를 탐색하면서 고른 숫자 갯수가 m이라면
    	//answer 배열을 출력한 후 dfs 탐색을 멈춘다
        return;
    }
    
    //dfs 탐색 로직
    for(int i = 1; i <= n; i++) {
        answer[idx] = i;		//answer배열의 idx번째 값을 i로 저장
        dfs(n, m, idx +1);		//고른 숫자의 총 개수가 1 증가했으니까, idx를 1 증가시킨 후 dfs 재귀 돌린다
    }
}

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        answer = new int[m];
        sb = new StringBuilder();
        
        dfs(n, m, 0);
    
        System.out.println(sb.toString());
    }
    
    private static int[] answer;
    private static StringBuilder sb;
    
    private static void dfs(int n, int m, int idx) {
        if(idx == m) {
            for(int num : answer) {
                sb.append(num + " ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i = 1; i <= n; i++) {
            answer[idx] = i;
            dfs(n, m, idx + 1);
        }
    }
}

[참고한 곳]
https://st-lab.tistory.com/115
https://velog.io/@fantastik/31
https://velog.io/@fantastik/32