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

---

안녕하세요

인포돈 입니다.

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

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

---

백준 15651번 (N과 M3)

문제

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

 

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

같은 수를 여러 번 골라도 된다.

 

입력

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

 

출력

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

 

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

 

입력 예시

3 1

출력 예시

1
2
3

입력 예시

4 2

출력 예시

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

입력 예시

3 3

출력 예시

1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
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 = 1 ; i <= M; i++) {
			arr[depth] = i;
			dfs(i,depth+1);
		}
		
	}
}

 N과 M 시리즈의 3번째 알고리즘입니다. 제가 백 트레킹 부분에서 이해가 잘 가지 않아 백 트레킹 관련 문제는 모두 다 풀어보기로 하였습니다.

 

이전에 제가 세웠던 공식 if와 for에 대해서 다시 한번 짚어보며 해당 문제에 대해서 STEP별로 나누어 설명해 드리겠습니다!

 

STEP별로 이해해가시면 됩니다!

---

알고리즘 흐름도

입력받기 -> stringToknizer을 통하여 입력값 구분 -> arr int배열을 선언하여 크기를 N으로 지정 -> dfs에 깊이 0 넣어주기 -> dfs를 통해 값들을 각각 arr에 저장 -> 깊이가 같아지면 sb에 값을 저장 -> sb출력

---

STEP1 되짚는 백 트레킹 이론

 어렵게 해석돼 놓은 것들이 많은데 간략히 "백 트레킹 = 나뭇가지"라고 이해하시면 됩니다. 일반적으로 나무는 한 뿌리에서 시작하지만 위로 갈수록 수많은 가지로 나뉘잖아요. 이처럼 백 트레킹은 여러 갈래로 나아가면서, 모든 수를 순회하는 기법입니다.

 

 백 트레킹에 여러 기법이 있는데 그중 오늘 저희가 사용한 DFS만 이해하시고 가면 됩니다. 이것도 간단합니다. deep first search 깊이 우선 탐색, 즉 한 나무의 모든 가지를 탐색하려 할 때 한 가지의 가장 깊은 곳에 있는 것부터 탐색하고 옆가지로 이동하는 방식이죠.

 

여기서 dfs에 대한 정의를 꼭 기억하시고 다음 dfs로 넘어가 보세요~

---

STEP2 DFS에서의 if와 for문

 DFS를 처음 접해본다! 하시는 분들은 처음에는 딱 이것만 기억하시면 돼요. DFS를 IF문과 FOR문 2개로 구성한다!

IF : 앞서 DFS에서 설명했듯이 깊이가 최종 깊이가 되면 DFS를 멈추는 역할을 합니다.

FOR : 앞서 DFS에서 설명한 깊이와 옆가지로 이동하는 역할을 합니다.

(FOR문 자체는 옆가지로 이동하는 역할 FOR문 안에 있는 dfs함수가 바로 깊이로 들어가는 역할을 담당한답니다)

 

그렇다면 해당 문제에서는 어떻게 적용되었는지 예제로 살펴보죠

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 = 1 ; i <= M; i++) {
			arr[depth] = i;
			dfs(i,depth+1);
		}
		
	}

... 글을 쓰다 발견했지만 인자로 받는 int a는 이제 보니 사용 안 하는 인자더라고요... a는 신경 쓰지 않으셔도 됩니다 ㅎㅎ

여기서 for문 먼저 설명해드리겠습니다.

 

이번 설명은 입력 예시 4 2 예제를 따릅니다.

 

FOR문

i의 경우 출력에 1부터 시작되기 때문에 넣어준 값!

depth의 경우 깊이 즉! arr배열의 크기가 바로 깊이로 볼 수 있지요. 몇 칸을 차지할 것인가!

천천히 따라가 봅시다.

depth에 0의 값을 할당해 준다면, arr [0]에는 1의 값이 들어가게 되죠,

for문이 다시 한번 돌기 이전에 dfs(i, depth+1) 이 실행되죠, 즉 dfs(1, 1) 여기서 앞서 a는 신경 쓰지 않으셔도 되니 a를 지우 서고 dfs(depth+1)로 쓰셔야 합니다.. ㅎㅎ

 

아무튼 깊이가 1개 더 높아졌지요 그러면 첫 번째 for문에서 i가 2로 가기 전에 dfs가 먼저 실행이 되죠

그렇게 되면 dfs가 실행돼 곳의 두 번째 for문이 실행되게 됩니다. 이전에 arr [0]에 1의 값이 들어갔고 이번에 depth가 1이 되니 arr [1]에 1의 값이 들어가게 되죠. 그리고 다시 한번 dfs를 실행하게 되면, 다음에 배울 if문에 걸리게 됩니다.

 

여기서 시간의 순서를 보여드리겠습니다.

 

main에서 호출된 dfs를 1번 dfs

1번 dfs에서 실행된 for문이 1번 for문이라고 지칭하겠습니다.

 

1번 dfs -> 1번 for문 (i=1) -> 2번째 dfs

-> 2번째 for문(i=1) -> 3번째 if문(3번째 dfs종료)     // 1 1이 sb에 저장

-> 2번째 for문(i=2) -> 3번째 if문(3번째 dfs종료)     // 1 2가 sb에 저장

-> 2번째 for문(i=3) -> 3번째 if문(3번째 dfs종료)     // 1 3이 sb에 저장

-> 2번째 for문(i=4) -> 3번째 if문(3번째 dfs종료)     // 1 4가 sb에 저장

이런 식으로 진행되며 마지막 i=4까지 진행되었다면, 해당 dfs메서드는 더 이상 할 일이 없기에 자동으로 종료가 됩니다.

 

그 이후 다시 1번 for문 (i=2)를 이와 같이 진행하게 됩니다. 이런 식으로 저희는 원하는 값을 넣을 수 있죠. 

 

IF문

if문의 경우 사실 간단합니다. 깊이가 앞서 입력받았던 N과 같아지면 sb에 arr배열을 넣어주기만 하면 끝나니 깐요. 대신에 해당 문장이 실행되고 반듯이 return을 통해 해당 dfs를 정지시켜줘야 합니다.

---

*변수설정 TIP

 여기서 변수 설정의 팁을 드리자면, 처음 알고리즘을 풀이할 때는 모든 변수를 다른 변수로 지정해 줍니다. 그리고 문제를 풀어보면서 같은 변수를 사용해도 될 거 같은 곳의 변수를 하나씩 지우면서 하시면, 쉽게 변수를 선언해 줄 수 있습니다.

 

백트레킹에 대한 더 쉬운 설명을 위해서 하단 링크의 문제풀이를 보시면 더 쉽게 이해하실 수 있습니다~

 

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

 

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