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

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

15652번: N과 M (4)

---

문제

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

입력

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

출력

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

입출력 예제

---

풀이방식

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

---

설계과정

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

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

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

4. 그 후에 재귀함수를 호출하는데, 이 때에 매개변수를 2개 넣어서 호출한다.

• 하나는 시작하는 수이고 하나는 깊이이다.
• 시작하는 수는 for문을 통해 증가하기에 그대로 넣어주고, 깊이는 1 더해서 넣어준다.

---

풀이과정

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

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

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

 

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

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

4. 입력받은 값부터 N까지 도는 for문을 작성해서 배열에 값을 넣고 재귀함수를 호출한다.

• 예제 출력에서 각 값들이 1부터 시작하는게 아니라 자기 자신부터 시작하기 때문에 입력받은 값인 v 부터 시작한다.
• i는 for문을 통해 증가하기에 그대로 넣어주고, 깊이인 depth는 1 더해서 넣어준다.

---

답안소스

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