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

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

15655번: N과 M (6)

---

문제

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

입력

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

출력

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

입출력 예제

---

풀이방식설계

[ DFS 중에서도 백트래킹에 대한 문제임을 인식하고 풀어보자. ]

 

1. 방문하지 않은 곳이라면 도달한 후에 방문했다는 값을 넣어주고, 다음 레벨로 넘어갈 때에 방문 여부를 초기화한다.

• 중복되지 않아야 하기 때문이다.

2. 방문하지 않은 곳이기에 결과를 출력할 배열에 값을 넣는다.

 

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

• 다음 레벨을 탐색하기 위한 시작 위치를 입력받은 배열의 다음 값으로 지정하는 것을 잊지말자.

4. 모든 레벨을 탐색했으면 결과를 출력한다.

---

풀이과정

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

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

2. 입력값들을 입력받아 저장한다.

 

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

 

4. 그게 아니라면 방문여부를 확인한다.

 

5. 방문하지 않았다면 방문여부인 ch를 1로 바꿔주고, graph[depth] 배열에 arr[i] 값을 넣어준다.

• 해당 레벨에 입력받은 값을 넣어서 추후에 출력하기 위함이다.

6. 해당 레벨에 탐색을 완료했다면 다음 레벨을 탐색하기 위해 depth+1과 i 를(을) 넣어서 DFS 재귀함수를 호출한다.

• 다음 레벨을 탐색하기 위한 시작 위치는 arr[i] 배열의 다음 값이다. 그러므로 i를 넣어서 arr에 들어간 입력받은 값들을 순차적으로 탐색하게 한다.

7. 다음 레벨을 탐색하기 위해 기존에 방문한 노드에 대한 방문여부인 ch를 0으로 변경해준다.

•  다시 탐색을 진행하기 위해서이다.

---

답안소스

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