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

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

15654번: N과 M (5)

---

문제

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

입력

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

출력

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

입출력 예제

---

풀이방식설계

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

 

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

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

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

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

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

---

풀이과정

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

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

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

• arr 배열에 값을 넣을 때 주의할 점은 토큰을 생성하는 것이다. BufferedReader를 사용하면 입력받은 값을 나누기 위해 StringTokenizer 를 사용하는데, 이 토큰을 설정하지 않은 상태에서 값을 입력하면 NoSuchElementException 에러가 발생한다. (이에 대한 설명은 추후에 따로 정리할 예정이다.)

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

 

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

 

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

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

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

 

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