[백준]15650번 - N과 M(2) (JAVA)

알고리즘 & 자료구조/완전탐색

[백준]15650번 - N과 M(2) (JAVA)

윤도ri 2022. 5. 9. 21:32

| 문제

이 문제는 1~ N까지의 수를 탐색하여 M개를 고르는 문제이다. 그러므로 우리는 정해진 숫자범위에서 탐색을 해야한다는 의미와 같다. 또한 이 말은 즉 백트래킹을 사용해야한다는 뜻이다.

| 백트래킹(Backtracking) 이란?

말 그대로 되추적한다 라는 의미이다. 좀 더 알고리즘적으로 설명하자면, 어떤 노드의 '유망성'을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가 다른 자식 노드를 찾는 방법이다. 즉, 모든 경우의 수를 찾아보지만, 그 중에서도 가능성만 있는 경우의 수를 찾아보는 방법이다. 백트래킹의 방법은 여러가지가 있지만 이번 문제에는 DFS 라는 알고리즘을 사용하게 될 것이다.

| DFS 란?

Depth-First-Search 의 약자이며 깊이를 우선 탐색한다는 의미이다.

- 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 하고 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행하는 방법이다.

- 모든 노드를 방문하는 경우에 이 방법을 사용한다.

| 풀이 접근 방식

1. N, M 을 입력값으로 받는다.

2. 중복되는 수를 제외한 모든 경우의 수를 탐색한다. ( 1 1 , 2 2 ( X) )

1) 재귀를 사용한다. (* 재귀함수란? 함수가 직접 또는 간접적으로 자신을 호출하는 프로세스)

2) 탐색하고 출력하기 위해서 값을 담을 int 배열 arr 를 생성한다.

3) M개를 다 고른후에는 더이상 재귀를 호출하지 않고 arr배열을 출력하고 return 해야한다. 이를 위해

depth 변수를 추가한다. 재귀가 깊어질 때마다 depth를 1씩 증가시켜 M과 같아지면 더이상 재귀를 호출하지

않도록 한다.

3. 고른 수열은 오름차순이어야 한다. ( 2 1 4 2 (X) )

앞서 N과 M (1)에서의 문제와 차이점은 오름차순이여야 한다는 것이다. 여기서 추가적으로 필요한것은 as 변수이다.

이 변수는 현재 위치, 즉 어디서부터 시작하는지를 의미하는 변수이다. 예를 들어 반복문에서 재귀를 해 줄때, as= 1 부터 시작하면 다음 재귀는 오름차순으로 탐색하기 위해 as를 1 증가시킨 2를 인자로 넘겨주면서 다음 재귀의 반복문이

2부터 시작하도록 하는 변수를 의미한다.

4. 공백을 구분해서 출력한다.

| 입출력

bufferedReader 와 StringBuilder를 사용했다. (성능의 차이를 고려하여)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class DFS_15650 {
	//N과 M은 값이 변경될 일이 없으므로 메소드 바깥에 선언해둔다. 
	public static int[] arr;
	public static int N, M;
	public static StringBuilder sb = new StringBuilder();
	
	
	public static void main(String[] args) throws IOException {
		//출력과 문자열 분리를 위해 사용
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[M];
		
		dfs(1,0);
		System.out.println(sb);
		
	}
	public static void dfs(int as, int depth) {
		//깊이가 M과 같을 경우 출력해준다. 
		if(depth==M) {
			for(int val : arr) {
				sb.append(val).append(' ');
				
			}
			sb.append('\n');
			return;
		}
		
		
		for(int i = as; i<= N; i++) {
		//현재 깊이를 index에 적고 해당 위치에 i 값을 담는다. 
			
			arr[depth] = i;
		//현재 i값보다 다음 재귀에서 커야하므로 i+1의 값을 넘겨주고 
		//깊이 또한 1 증가시켜 재귀 호출한다. 
			
			dfs(i+1, depth+1);
		}
	}

}

참고: https://st-lab.tistory.com/115