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

안녕하세요

인포돈 입니다.

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


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

---

백준 15649(N과 M2)

문제

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

 

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

고른 수열은 오름차순이어야 한다.

입력

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

출력

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

 

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

 

입력 예시

3 1

출력 예시

1
2
3

입력 예시

4 2

출력 예시

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

입력 예시

4 4

출력 예시

1 2 3 4

성공 코드

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

public class Main {
	public static int N, M;
	public static StringBuilder sb = new StringBuilder();
	public static int[] arr;
	
	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(0, 1);
		System.out.println(sb);
	}
 
	public static void dfs(int depth, int a) {
 
		if (depth == M) {
			for(int t : arr) {
				//if(t==0) break;
				sb.append(t).append(" ");
			}
			sb.append("\n");
			return;
		}
        
		for (int i = a; i <= N ; i++) {
			arr[depth] = i;
			dfs(depth+1,i+1);
		}
	}
}

N과 M2 알고리즘에서 생각해야 될 점은 바로 백 트레킹에 관한 점입니다. 저 또한 백 트레킹 알고리즘을 풀이해 나갈 때마다 아직 너무 헷갈리고 어려운 건 사실이지만, 하다 보면 언젠가는 익숙해질 거라고 생각합니다.... ㅋㅋㅋ

 

우서 해당 백 트레킹을 이해하기 위해서 STEP을 따라가면 되지만, 그전에 아주 간단한 점을 하나 기억하고 가시길 바랍니다.

public static void DFS(parameter){

	if(){
    	~~	//	깊이가 어느정도 깊어지면 해당 dfs를 끝내는 문장
    }
    
    for(){
    	~~	//재귀를 위한 문장
    }

}

DFS를 구현할 때 해당 사항을 항상 기억해 줘야 합니다. 각 문제마다 IF와 FOR문에 들어가는 조건과 반복문은 다르겠지만 큰 틀을 항상 기억해 두셔야 합니다.

---

알고리즘 흐름도

입력받기 -> 받은 입력으로 출력할 배열 크기 지정 및 DFS에 사용할 변수 선언하기 -> DFS FOR문 작성 -> DFS IF문 작성 -> 출력하기

---

STEP1 입력 배열에 넣기

StringTokenizer st = new StringTokenizer(br.readLine());
 
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
 
		arr = new int[M];

역시나 저희는 이번에도 입력 예제 하나를 이용해서 쉽고 간단히 이해할 수 있게 이해를 도와 드릴 꼐요 저희가 사용할 입력은 바로 4 4

 

여기서 4 4를 의미하는 바를 생각해보면, 앞에 있는 4는 깊이를 나타내죠, 웬 깊이냐고요??? 쉽게 이해하시려면, 그냥 1 ~ 4까지의 숫자를 사용할 수 있음을 의미하죠

 

뒤에 있는 4는 저희가 출력할 숫자의 개수가 됩니다. 이 말은 즉, 배열의 크기로 생각해 볼 수 있겠죠~?

(왜냐하면 저희가 사용할 숫자의 크기를 4로 설정하면 되기 때문이죠.)

 

따라서 입력받은 문자열 4 4를 각각 N과 M에 저장해줍니다.

 

 => 그 뒤 int [] arr에 크기가 M인 배열을 생성해 줍니다. arr배열이 바로 저희가 출력에 사용할 배열이죠

 

---

STEP2 DFS 구현하기

 

이 제 정말로 가장 주 용한 DFS를 구현할 때입니다. 조금 어려우니 잘 따라오시면 됩니다.

 

---

STEP 3 DFS FOR문 작성하기

	public static void dfs() {
 
		if () {

		}
        
		for () {

		}
	}

자 앞서 배웠던 DFS의 기본 형식입니다. 우선 FOR문부터 채워 봅시다. FOR문은 재귀를 사용할 때 이용됩니다. 재귀란 백 트레킹의 주요 기술로 자기 자신을 또 한 번 호출하여 계속하여 깊이를 더해가는 방법입니다. 쉽게 말해서 인셉션처럼 꿈에 꿈으로 들어가는 것이라고 생각해보세요 ㅎㅎ

 

우선 FOR문에 어떻게 돌려야 할까요?

 

이해하기 쉽게 하려면 저희는 4 4 앞에 있는 4족 1 ~ 4까지의 숫자를 반복해서 들어가야 합니다. 좀 더 이해하기 쉬운 실려면 트리를 손으로 직접 작성해 보셔야 합니다.

 

해당 문제를 해결하기 위해서 0의 값부터 시작하는 게 아니라 1부터 시작하게 되죠. 그다음 어느 깊이까지 들어가야 하냐면 바로 N까지 즉4까지의 숫자로 반복을 해야 합니다.

 

	public static void dfs() {
 
		if () {

		}
        
		for (int i = 1; i <= N ; i++) {

		}
	}

조건은 다음과 같게 되겠죠! 그다음 생각할 것은 FOR문 안의 문장입니다. arr이 저희가 출력해야 할 문장입니다. 그렇다면 처음에 1부터 채워보면 arr [0]에 1의 값을 넣어줘야 합니다.

	public static void dfs() {
 
		if () {

		}
        
		for (int i = 1; i <= N ; i++) {
		arr[0] = i;
		}
	}

어?? 그런데 해당 식처럼 작성을 해버리면 계속 반복을 해도 arr [0]에 값만 변경이 되게 되죠. i는 1부터 시작하니 해당 값을 계속해서 변경할 수 있게 변수로 선언해 주어야 합니다. 그런데 해당 변수를 dfs안에 선언하게 된다면 재귀를 통해서 해당 변수를 계속해서 초기화해주게 되죠. 따라서 해당 변수는 dfs함수 밖에 선언을 해주어야 합니다.

 

그렇게 되면 저희는 dfs의 parameter로 변수 a를 설정해 주도록 합시다.

	public static void dfs(int a) {
 
		if () {

		}
        
		for (int i = 1; i <= N ; i++) {
			arr[a]=i;
            dfs(a+1);
		}
	}

여기서 저희는 arr [0]에는 1의 값이 들어가게 되죠. 이를 반복하게 된다면 arr [0]에는 각 값이 1 2 3 4가 들어가게 됩니다. 이 때 i의 값이 바뀌기 전에 재귀를 해주어 arr[0] = 1 일 때 다음 재귀로 넘어가게 되죠.

이때 a+1을 해준 이유는 바로 arr [1]의 값을 넣어주기 위해서이죠. 그렇게 해서 값이 들어가면 그다음 arr [2]에는 1 ~ 4의 값이 들어가게 되죠. 이상하게 생각이 되죠??

 

첫 번째 i=1일 때 재귀를 생각해보면 1111, 1211, 1311, 1411, 1121.... 이런 식으로 모든 값이 arr에 저장되게 되죠. 그렇게 되면 안 되는 저희는 한 가지 규약을 더 가해 줍니다. 바로 depth라는 변수를 하나 더 선언해 줍니다.

	public static void dfs(int depth, int a) {
 
		if () {

		}
        
		for (int i = a; i <= N ; i++) {
			arr[depth] = i;
			dfs(depth+1,i+1);
		}
	}

depth 또한 dfs안에 선언할 경우 계속하여 초기화하기 때문에, 밖에 선언 후 parameter로 받아오는 형식이 되죠. 자 그러면 해당 코드가 갑자기 변경되어 이해하기 어려우실 수 있습니다. 트리로 생각해 보시기 바랍니다. 아래 그림과 같이 말이죠

dfs를 말로 서술하기란 너무 어려운 거 같습니다 ㅜㅜ 이런 식으로 첫 번째 for문에서 i가 1 ~ 4까지 반복을 하면서 각 번호에 맞는 arr [0]의 값을 저장하고 재귀로 들어가게 됩니다. 평행 세계 느낌으로 첫 번째 i=1일 때는 arr [0]=1이 되고 그 아래로 갈수록 arr [1], arr [2]. arr [3]의 값들이 저장되게 되죠. 그러나 저희는 항상 depth를 생각해 봐야 합니다. 따라서 제가 x를 친부분은 바로 if문에 의해 걸러지기 때문에 해당 값들을 x를 치게 되었죠.

---

STEP 4 DFS IF문 작성하기

 
	public static void dfs(int depth, int a) {
 
		if (depth == M) {
			for(int t : arr) {
				//if(t==0) break;
				sb.append(t).append(" ");
			}
			sb.append("\n");
			return;
		}
        
		for (int i = a; i <= N ; i++) {
			arr[depth] = i;
			dfs(depth+1,i+1);
		}
	}

간단합니다. 해당 식은 depth가 M이라면 즉 4라면 sb에 해당 값들을 형식에 맞게 복사 붙여 넣기를 한 후 return을 통해 dfs를 종료시킵니다. 그렇게 되면 여러 갈래로 나아갔단 dfs가 하나씩 종료를 하게 됩니다. 그러나 depth==M을 만족하기 우해서는 depth가 M이 되어야 합니다. 그러나 앞서 살펴본 트리에서 차례대로 1 2 3 4가 출력되지 않은 경우 i가 4가 넘어가게 되어 for문이 작동하지 않게 됩니다. 그렇게 되면 재귀가 되지 않아 depth는 영원히 4의 값을 갖지 않게 되죠. 이후에 첫 번째 i가 1일 경우만 살펴보았는데

 

이 외에 2 3 4를 이와 같은 형식으로 진행을 해도 결국에는 1 2 3 4만 출력됨을 알 수 있게 되죠.

 

 

---

STEP 5 출력하기

해당 sb의 값을 출력하기만 되기 때문에 pass~

 

=> 추가적으로 main함수에서 dfs(0, 1)을 넣어주어 depth는 0부터 초기 값 a는 1부터 시작되어 차례로 진행되게만 넣어주면 끝~~