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

안녕하세요

인포돈 입니다.

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


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

---

백준 15649 (N과 M1)

문제

자연수 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 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

입력 예시

4 4

출력 예시

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

성공코드

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

public class Main {
	 static StringBuilder sb = new StringBuilder();
	 static boolean[] visit;
	 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());
	   	 	
	   	 	int N = Integer.parseInt(st.nextToken());
	   	 	int M = Integer.parseInt(st.nextToken());

	   	 	arr = new int[N];
	   	 	visit = new boolean[N];
	   	 	backtracking(N, M, 0);
	   	 	System.out.println(sb.toString());
	}
	
	public static void backtracking(int N, int M, int depth) {
		
		if (depth == M) {
			for (int val : arr) {
				if(val==0) break;
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (!visit[i]) {
				visit[i] = true;
				arr[depth] = i + 1;
				backtracking(N, M, depth + 1);
				visit[i] = false;
			}
		}
	}
}

N과 M1 알고리즘은 처음 접해보는 알고리즘이었습니다.... 문제의 이해는 쉬웠지만, 어떻게 문제를 풀이해야 할지 몰라 다른 분들의 코드를 많이 참고해보았습니다. 물론 처음에는 저도 내용 이해가 쉽지 않더라고요. DFS가 무엇인지는 알았지만, 이런 식으로 해결할 수 있는지도 몰랐습니다. 하나하나 저랑 같이 풀이해 봅시다.

 

---

알고리즘 흐름도

입력받기 -> 반복문으로 가장 상위 숫자들 배열에 입력 -> 각 배열 BACKTRACKING으로 하위 노드 입력 ->  해당 배열 출력 -> 반복

---

STEP1 입력받기

	   	  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());

	   	 	arr = new int[N];
	   	 	visit = new boolean[N];
	   	 	backtracking(N, M, 0);

뭐 입력받기는 사실 쉽습니다. 그러나 여기서 입력받은 두 숫자를 각각 N과 M으로 나누어 변수에 넣어주어야 해당 알고리즘을 쉽게 풀이할 수 있죠

 

여기서 arr배열의 경우 우리가 직접 출력할 배열이며 visit은 우리가 들렸던 노드를 체크하는 역할을 하죠 즉, 만약에 앞의 예시에서 4 2의 입력이 들어오면 해당 체크를 안 해주면

1 1

1 2

1 3

이런 식으로 출력이 됩니다. 왜냐하면 방문했던 곳도 같이 방문하여 1 1이 출력하기 때문이죠. 이러한 문제를 해결하기 위해 visit배열을 사용한답니다~

---

STEP2 반복문 돌리기

public static void backtracking(int N, int M, int depth) {
		
		for (int i = 0; i < N; i++) {
			if (!visit[i]) {
				visit[i] = true;
				arr[depth] = i + 1;
				backtracking(N, M, depth + 1);
				visit[i] = false;
			}
		}

여기서 for문은 어떤 역할을 하냐가 중요합니다. 앞서 말했듯이 저희는 visit을 통해서 중복되는 숫자를 제거해줄 수 있습니다. 첫 번째 예시로 3 1을 생각하기보다는 4 2로 생각하시는 게 훨씬 이해하기에 편리하게에 설명드리겠습니다.

 

자 N=4, M=2, depth=0으로 값을 넣어주어 들어옴을 알 수 있습니다. (앞선 step1에서 이런 식으로 입력을 넣어주었기 때문입니다.)

 

그렇다면 for문은 여기서 무슨 역할을 하는지 알아보죠

 

일단 for문은 N번째 까지만 진행을 합니다. 즉, 0부터 ~ 3까지 4번을 반복하죠. 즉 우리가 출력하는 숫자가 4를 넘지 않게 설정해 주었죠

 

두 번제 if문의 경우 앞서 설명한 것처럼 반복되는 숫자가 들어오면 if문을 실행하지 못하게 하는 코드!

만약에 해당 코드를 통과했다면, 바로 해당 visit을 true로 바꾸어주어 중복되는 값이 들어오지 못하게 합니다!

 

그 후 arr [0]에다가 1을 입력하게 되죠

 

그다음에 다시 백 트레킹 메서드에 depth를 1 올려주어 다시 들어옵니다.

그러면 아직까지는 아래에 있는 visit [i] = false'는 실행되지 않은 상태입니다.

 

자 다시 백 트레킹으로 들어옵니다. depth는 그럼 이제 1의 값을 가지게 되죠? 똑같은 방법으로 해당 for문을 들어갑니다. 그러면 i가 0일 때는 앞서 visit배열 0인 덱스에 true의 값이 있기 때문에 if문을 통과하지 못하죠!

 

그렇게 되면 이제 i가 1일 때를 보면 arr [1]에는 값이 2가 들어가게 되죠.

 

즉 arr배열에는 1과 2의 값이 들어가 있게 됩니다. 계속해서 for문을 돌리게 되면 arr 값에는 1 2 3 4의 값이 쌓이게 되죠. 그런데 저희는 

1 2

1 3

1 4

2 1

2 3

.... 이런 식으로 출력을 해야 하죠! 이러한 문제는 바로 아래 STEP 3에서 해결을 해볼 수 있습니다 ~

---

STEP 3 BACKTRACKING 설정하기

	public static void backtracking(int N, int M, int depth) {
		
		if (depth == M) {
			for (int val : arr) {
				if(val==0) break;
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (!visit[i]) {
				visit[i] = true;
				arr[depth] = i + 1;
				backtracking(N, M, depth + 1);
				visit[i] = false;
			}
		}

자 앞서 본 for문과 함께 if문을 생각을 해보게 됩니다.

 

앞서 저희는 arr에 1 2 3 4의 값이 들어가게 됩니다. 그러나 해당 값을 정확히 출력하기 위해서는 이제 저희가 입력받았던 M을 활용해야 합니다. 만약 depth가 M과 같게 된다면 해당 값을 sb(StringBuilder)에 값을 추가해 줍니다. 그렇다면 저희가 처음으로 생각했던 1 2 3 4의 값에서 저희는 1 2의 값만 arr에 넣은 상태에서 이 if문에 걸리게 되죠. 그렇게 되면, 1과 2의 값을 sb에 저장한 후 return을 해줍니다. 여기서 return은 이제 해당 트래킹을 종료시키는 상황이 벌어지게 되죠.

 

그렇다면 이제 저희는 생각해봐야 합니다?? 어랏 그러면 이런 식으로 하면 어떻게 생각해야 되지???

 

머릿속으로 정리하시기 힘드신 분을 위해 제가 간단한 그림으로 설명해드리겠습니다.

 

인셉션처럼 해당 알고리즘이 작동함을 인지해야 합니다.

이런 식으로 backtracking이 일어나게 되죠.

backtracking이 처음 들어왔을 때는 가장 선두 node인 0 1 2 3이 반복이 되고

첫 선두 node인 0이 다시 한번 backtracking이 들어가 그 안의 for문에서 2 3 4가 반복되어 arr에 값이 저장이 되죠.

 

저장되는 값들은 모두 sb에 저장이 되는 것이고요

 

이런 식의 반복을 통해서 해당 값들을 출력할 수 있죠.

---

STEP 3 출력하기

System.out.println(sb.toString());

뭐 출력은 간단하죠. 해당 backtracking이 끝날 경우 해당 값들은 모두 sb에 저장되어있기 때문이죠.

 

물론 처음 backtracking을 접하면 헷갈리실 겁니다. 항상 순서를 처음부터 차례차례 따라가면 어렵긴 해도 이해가 되긴 하죠. 항상 이런 backtracking을 할 때는 depth를 고려해줘야 합니다. 이런 depth가 너무 깊게 들어가게 되면..... 당연히 오류가 나거든요 ㅎㅎ

---