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

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

---

문제 링크

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

문제 풀이

✔ 입출력 및 요구사항 확인

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

✔ "중복 없이 M개를 고른다" 의 의미

중복 없이 M개를 고르기 위해서는 이전에 탐색했는지 여부를 저장해주어야 합니다. dfs로 1부터 N까지 모든 수를 탐색하되, visited 배열을 이용해서 이전 탐색 여부를 저장해주면 됩니다. 탐색한 값은 answer배열에 저장해줍니다.

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

이전에 풀었던 N과 M (1) 문제에서는 "1 2"와 "2 1"을 다른 경우로 체크했습니다. 하지만 이번 문제는 고른 수열이 오름차순이므로, "1 2"와 "2 1"이 모두 "1 2"로 똑같습니다. 해당 요구사항은 dfs함수 속 for문의 index를 조절하면 됩니다.

✔ 핵심 코드

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

boolean[] visited = new boolean[n+1];
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문을 수행
    	if(visited[i] == false) {	//아직 i값을 탐색하지 않았다면
            visited[i] = true;		//i를 탐색한다
            answer[idx] = i;		//answer배열의 idx번째 값을 i로 저장
            dfs(n, m, idx +1, i+1);	//고른 숫자의 총 개수가 1 증가했으니까, idx를 1 증가시키고, 현재 탐색한 i값보다 1 증가시킨 값을 at으로 바꿔서 dfs를 수행한다
            visited[i] = false;		//dfs가 모든 경우의 수를 탐색해야하므로 해당 재귀함수가 완료된 후 탐색여부를 false로 바꾼다
        }
    }
}

전체 코드

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());
        
        visited = new boolean[n+1];
        answer = new int[m];
        sb = new StringBuilder();
        
        dfs(n, m, 0, 1);

        System.out.println(sb.toString());
    }
    
    private static boolean[] visited;
    private static int[] answer;
    private static StringBuilder sb;
    
    private static void dfs(int n, int m, int idx, int at) {
        if(idx == m) {
            for(int num : answer) {
                sb.append(num + " ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i = at; i <= n; i++) {
            if(visited[i] == false) {
                visited[i] = true;
                answer[idx] = i;
                dfs(n, m, idx + 1, i + 1);
                visited[i] = false;
            }
        }
    }
}

---

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