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

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

15657번: N과 M (8)

---

문제

• N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 
• N개의 자연수는 모두 다른 수이다.
• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 비내림차순이어야 한다.
• 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

• 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
• 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

입출력 예제

---

풀이방식설계

[ DFS에 대한 문제임을 인식하고 풀어보자. ]

 

1. 배열에 입력받은 자연수들을 넣고 정렬한다.

 

2. 해당 레벨에 대한 탐색을 완료하였으면 재귀함수를 호출해 다음 레벨을 탐색한다.

• 각 레벨에서 자기 자신을 포함한 경우의 수열을 출력해야 하기에 중복 관련 코드는 없다.
• for문을 돌릴 때, 시작 값을 입력받은 배열 값으로 줘야 다음 레벨로 갈 때 맨 처음 배열 값을 제외하고 탐색한다.

3. 레벨이 M과 동일하지 않다면 탐색을 계속하고, 동일하다면 결과를 출력한다.

---

풀이과정

1. 사용한 변수들은 다음과 같다.

• graph[ ] : 결과값을 저장할 배열(M 개씩 출력해야한다.)
• arr[ ] : 입력값을 저장할 배열

2. arr 배열에 입력값들을 저장하고 정렬한다.

 

3. for문을 통해 탐색을 진행하며 graph 배열에 arr[i] 값을 넣어준다.

• 반복에서 시작 값을 입력받은 배열 값으로 줘야 다음 레벨로 갈 때 맨 처음 배열 값을 제외하고 탐색한다.
• 입력받은 수들이 조건에 일치하다면 결과값으로 출력하기 위해 graph 배열에 값을 넣어준다.

4. 해당 레벨에 탐색을 완료했다면 `(depth + 1, i)` 파라미터를 넣어서 DFS 재귀함수를 호출한다.

• 해당 레벨에 대한 모든 경우를 탐색했으므로 다음 레벨로 넘어가기 위해 레벨을 더해준다.
• 입력받은 숫자중에서 이전에 탐색한 숫자를 제외하고 다음 레벨로 넘어가야 하기 때문에 i를 파라미터에 넣는다.

5. depth가 M과 동일하지 않다면 탐색을 계속한다.

 

6. depth가 M과 동일하다면 모든 레벨을 탐색한 것이기에 출력한다.

---

답안소스

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

public class Main {
	static int N, M;
	static int[] graph, arr;
	static StringBuilder sb = new StringBuilder();
	
	public void DFS(int depth, int value) {
		if(depth == M) {
			for(int x : graph) {
				sb.append(x + " ");
			}
			sb.append("\n");
		} else {
			for(int i=value; i<N; i++) {
				graph[depth] = arr[i];
				DFS(depth + 1, i);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		Main eit = 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];
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		eit.DFS(0, 0);
		System.out.println(sb);
	}

}