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

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

---

문제 링크

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

문제 풀이

✔ 입출력 및 요구사항 확인

1부터 N까지 자연수 중 M개를 골라야 하고, 같은 수를 여러 번 골라도 됩니다. 또한 고른 수열은 오름차순이어야 합니다.

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

같은 수를 여러 번 고르기 위해서는 모든 경우를 탐색해야 합니다. 따라서 N과 M (3) 문제처럼 visited 배열을 이용할 필요가 없습니다.(visited 배열로 방문여부를 체크할 필요가 없습니다.)

✔ "고른 수열이 오름차순이다" 의 의미

이전에 풀었던 N과 M (2) 문제처럼 "1 2"와 "2 1"을 모두 "1 2"로 똑같이 체크해야 합니다. 해당 요구사항은 dfs함수 속 for문의 index를 조절하면 됩니다.

✔ 핵심 코드

두 가지 요구사항을 반영한 핵심 코드는 다음과 같습니다.

int[] answer = new int [m];

//n = 탐색해야 할 자연수(1부터 n까지)
//m = 골라야 하는 숫자의 갯수
//idx = 현재까지 dfs함수를 탐색하면서 골라둔 숫자의 갯수
//at = 탐색을 시작해야 하는 숫자
dfs(int n, int m, int idx, int at) {
    //dfs 탐색을 멈추는 로직
    if(idx가 m과 같다면) {	//dfs를 탐색하면서 고른 숫자 갯수가 m이라면
    	//answer 배열을 출력한 후 dfs 탐색을 멈춘다
        return;
    }
    
    //dfs 탐색 로직
    for(int i = at; i <= n; i++) {	//at부터 n까지 for문을 수행
    	answer[idx] = i;		//answer배열의 idx번째 값을 i로 저장
        dfs(n, m, idx +1, i);		//고른 숫자의 총 개수가 1 증가했으니까, idx를 1 증가시키고, 현재 탐색한 i값을 at으로 바꿔서 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, 1, 0);
    
        System.out.println(sb.toString());
    }
    
    private static int[] answer;
    private static StringBuilder sb;
    
    private static void dfs(int n, int m, int at, int idx) {
        if(idx == m) {
            for(int num : answer) {
                sb.append(num + " ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i = at; i <= n; i++) {
            answer[idx] = i;
            dfs(n, m, i, idx + 1);
        }
    }
}

---

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