[백준 알고리즘 자바] 15651 : N과 M (3)

https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

---

문제

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

출력

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

입출력 예제

---

풀이방식

이번 문제는 DFS에 대한 문제이다.

---

설계과정

1. 전역으로 각 변수를 선언하고, main에서 초기화한다.

2. depth와 M이 같으면 출력한다.

3. depth와 M이 다르면 입력받은 값부터 N까지 돌면서 배열에 값을 넣는다.

4. 그 후에 재귀함수를 호출하는데, 이 때 해당 깊이를 다 탐색했으면 깊이를 1 더해서 다음 값을 탐색하도록 한다.

---

풀이과정

1. 전역으로 변수를 선언하고 main에 코드를 작성한다.

• 값 입력받고, 함수 호출하고, 결과를 출력하는 코드이다.
• graph[ ] : 결과값을 저장할 배열이다.
• depth : 깊이(=레벨)을 의미한다.

2. 바로 DFS() 메소드 구현으로 넘어가보자.

 

3. depth 와 M 이 동일하면 graph 배열에서 값들을 꺼내 출력한다.

• depth와 M이 동일하다는 것은 마지막 노드에 도달했다는 것을 의미한다.

4. 동일하지 않다면 graph[] 배열에 i 값을 넣어주고, depth를 1씩 더해서 재귀함수를 호출한다.

• graph[] : 결과값을 저장할 배열이다.
• 해당 깊이에 대한 탐색을 마쳤으면 다음 깊이를 탐색한다.

5. 이해를 위해 스택에 들어가는 순서와 함께 코드를 정리해보자.

---

1. 맨 처음 값이 들어가면, depth == M 이 성립하지 않기에 else 문으로 넘어가서 for문이 실행된다. 과정은 아래와 같다.

1) DFS(0) 실행2) i에 1, depth에 0 이 들어가서 for문 수행3) graph[0] = 1 값이 들어감4) 다음 행에서 DFS(1) 호출

2. 스택의 가장 상단에 있는 함수가 수행되어야 하므로 이제 DFS(1)이 수행된다.

1) DFS(1) 수행

2) i에 1, depth에 1이 들어가서 for문 수행

3) graph[1] = 1 값이 들어감

4) 다음 행에서 DFS(2) 호출

3. 스택의 가장 상단에 있는 함수가 수행되어야 하므로 이제 DFS(2)이 수행된다.

1) DFS(2) 수행

2) depth 가 2로, M과 같기에 return 되며 DFS(2) 종료

3) DFS(2)가 스택에서 빠짐

4) 가장 상단의 DFS(1) 호출

4. DFS(1)이 호출될 때에 저장되어 있는 복귀 주소인 21 라인으로 돌아간다.

1) DFS(1) 수행

2) 21 라인으로 돌아가서 그 다음 라인 즉, i 를 증가시키며 for문을 수행한다.

3) i = 2, depth = 1 값이 들어감

4) 다음 행에서 DFS(2) 호출

5) depth 가 2로, M과 같기에 return 되며 DFS(2) 종료

6) DFS(2)가 스택에서 빠짐

7) 가장 상단의 DFS(1) 호출 > i를 증가시키며 for문 수행

5. 위 과정이 for문이 끝나는 시점 즉, i 가 4가 되는 시점까지 반복된다. 그 후에 스택에 남아있는 DFS(0) 이 수행된다.

1) DFS(0) 수행

2) i = 2, depth = 0 값이 들어감

3) 4번과 동일한 과정을 거쳐서 결과를 출력함

---

답안소스

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

public class Main {
	static int N, M;
	static int[] graph;
	static StringBuilder sb = new StringBuilder();
	
	public void DFS(int depth) {
		if(depth == M) {
			for(int x : graph) {
				sb.append(x).append(" ");
			}
			sb.append("\n");
			return;
		} else {
			for(int i=1; i<=N; i++) {
				graph[depth] = i;
				DFS(depth+1);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		Main three = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		graph = new int[M];
		
		three.DFS(0);
		System.out.println(sb);
	}
}