[백준-JAVA]15652번 풀이(N과M 4 알고리즘) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 15625번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 15652 (N과 M4)

문제

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

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비 내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤... ≤ AK-1 ≤ AK를 만족하면, 비 내림차순이라고 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

입력 예시

3 1

출력 예시

1
2
3

입력 예시

4 2

출력 예시

1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

입력 예시

3 3

출력 예시

1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

성공코드

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

public class Main {

	static int[] arr;
	static int depth;
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int M;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		
		dfs(1, 0);
		System.out.println(sb.toString());
}
	public static void dfs(int a, int depth) {
		
		if(depth == N) {
			for(int i = 0 ; i < arr.length ; i++) {
				sb.append(arr[i]).append(" ");
			}
			sb.append("\n");
			return;
		}
		
		for(int i = a ; i <= M; i++) {
			arr[depth] = i;
			dfs(i,depth+1);
		}
		
	}
}

 이제는 N과 M 4를 풀어보신 분이라면 이전 단계인 N과 M 1 2 3 시리즈를 풀었으리라 생각합니다. 그렇다면 이제는 DFS기본적인 부분은 이해하지 못하셨더라 하더라도 조금은 익숙해지셨을 것입니다. 그렇다면 이번 4 시리즈의 문제는 굉장히 쉽게 풀어보실 수 있었을 것입니다. 그래도 혹시나 이해가 안 가시는 분들은 이전 포스트의 문제를 먼저 풀어보시면 이해가 쉽게 됩니다!

 

[백준알고리즘-JAVA]15649번 풀이(N과M1) - 초보도 이해하는 풀이

 

[백준알고리즘-JAVA]15649번 풀이(N과M2) - 초보도 이해하는 풀이

 

[백준알고리즘-JAVA]15651번 풀이(N과M3) - 초보도 이해하는 풀이

이번 글에서는 간단하게 DFS에 대해서 되짚어보는 시간이 될 거 같네요

---

STEP1 이제는 기본은 익숙해진 DFS 되짚어보기

DFS가 트리구조를 가지며, 점점 아래 깊이로 내려가면서, 수많은 가지를 순회하며 모든 경우의 수를 찾아본다는 것을 알 수 있었지요. 그런데 곰곰이 생각해보면, for문을 중첩으로 이용해서도 tree순회를 가능하게 해 주지요. 그러나 여기서 중첩 for문과 DFS의 굉장한 차이점이 하나가 있습니다.

 

물론 성능적인 문제도 있지만,

 

우리는 초보자를 위해 쉽게 이해를 해야 합니다. 예시만큼 쉽게 이해할 수 있는 방법도 없지요

 

 첫 번째 예) : 피보나치수열 (f(n) = f(n-1) + f(n+2))

 

이런 식의 경우 함수의 인자만 바꾸어 넣어주면 간단히 해결되는 문제!! 만약에 반복문을 이용한다면, 풀이할 수야 있겠지만 코드가 복잡해지는 단점이 생기게 됩니다. (상대적으로 재귀 방법(dfs) 보다)

 

두 번째 예) : N만큼 굴려 나온 주사위의 경우의 수 구하기

여기서 저희가 주목해야 될 점은 바로 N만큼 있니다.

 

만약 N이 2라면 반복문을 2번 중첩하여 표현해야 합니다.

그러나 N이 미지의 수입니다. 그렇다면 프로그래밍을 할 때 FOR문을 어떻게 적용시켜야 할지 

모르게 됩니다.

이럴 경우는 재귀, 백 트레킹 (DFS)를 사용하여 풀이해야 되는 경우가 됩니다.

 

이외에도 수많은 방법이 재귀 용법으로 사용되어 풀이가 되는데, 언제나 재귀가 좋은 방법은 아닙니다. 경우에 따라 알맞은 알고리즘을 적용시키기 위해서는 역시... 수많은 문제들을 접해보고 풀어봐야 할 거 같네요... ㅎㅎ

 

이번 N과 M 시리즈로 DFS를 간단히 요약하자면 아래의 내용만 기억하세요

 

DFS를 기본적인 형식

 

public static void DFS( parameter ){

if() //깊이 판별하여 dfs종료시키는 역할



for() //경우의 수를 모두 순회하며 재귀를 하는 역할

}

 * 2차원 배열을 1차원 배열 + DFS 기법을 통하여 해결할 수 있다는 것도 참고해두시기 바랍니다.