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

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

15650번: N과 M (2)

---

문제

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

입력

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

출력

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

입출력 예제

---

풀이방식

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

---

설계과정

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

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

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

4. 그 후에 재귀함수를 호출하는데, 이 때 시작하는 위치와 깊이를 1씩 더해서 다음 값을 탐색하도록 한다.

5. 해당 문제는 중복여부를 체크할 필요가 없으므로 해당 코드는 제외한다.

---

풀이과정

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

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

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

 

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

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

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

• graph[] : 결과값을 저장할 배열이다.
• cn은 현재 노드 즉, 시작 위치로 중복을 없애기 위해 해당 값부터 시작한다.
• 중복 없이 이전 값보다 더 큰 수를 탐색하기 위해 재귀 함수를 호출할 때에 시작 위치와 깊이를 1씩 더해준다.

5. 아래 표를 통해 코드로 인해 반복되는 작업과 결과를 확인해보자.

• DFS(A,B) 는 함수가 호출될 때에 들어가는 인자의 값이다.
• DFS(2,1)이 호출되고 for문을 통해 해당 함수가 끝이 나면, i가 증가하며 DFS(3,1)이 호출된다.
• i 가 증가하며 노드의 끝인 4에 도달하면 depth를 증가시켜 다음 인자값을 넣고 재귀함수를 호출한다.

---

답안소스

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

public class Main {
	static int N, M;
	static int[] graph;
	static StringBuilder sb = new StringBuilder();
	
	public void DFS(int cn, int depth) {
		if(depth == M) {
			for(int x : graph) {
				sb.append(x).append(" ");
			}
			sb.append("\n");
			return;
		} else {
			for(int i=cn; i<=N; i++) {
					graph[depth] = i;
					DFS(i+1, depth+1);
				}
			}
		}
	
	public static void main(String[] args) throws IOException {
		Main two = 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];
		
		two.DFS(1, 0);
		System.out.println(sb);
	}
}