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

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

15663번: N과 M (9)

---

문제

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

입력

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

출력

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

입출력 예제

---

풀이방식설계

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

 

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

 

2. before 변수를 선언하고 0으로 초기화한다.

• 중복 수열을 없애기 위해서이다.

3. 중복된 값이 아니라면 방문 여부를 체크하고, graph[ ] 배열에 값을 넣고 before 변수에도 값을 넣는다.

• before 변수에 arr[ i ] 값을 넣어서 해당 레벨에서 중복되는 값이 없도록 한다.

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

 

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

---

풀이과정

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

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

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

 

3. before 변수를 선언하고 0으로 초기화한다.

• 해당 변수는 중복을 제거하기 위한 변수이다.
• for문 밖에 선언해서 해당 레벨에 대한 탐색이 끝나고 다음 레벨로 갈 때마다 0으로 초기화한다.

4. ch[ ] 배열에 1을 넣어서 방문 여부를 저장하고 graph[ ] 배열에 값을 넣는다.

 

5. before 변수에 arr[ i ] 값을 넣는다.

• 중복되는 수열을 제거하기 위한 과정이다.
• 아래 코드를 통해 자세히 알아보자.

1. before 변수를 0으로 초기화하고 for문을 수행한다. 이 때 각 변수들은 아래와 같다.

for문을 수행하면 before 값은 당연이 0이다. 그리고 ch 배열에 방문 여부 값으로 1을 넣고, graph 배열에 값을 넣는다.

그리고 arr[ i ] 값을 before에 넣는다. 그러면 아래와 같은 표가 완성된다.

(편의상 arr 배열에 값이 들어간 후를 before2 라고 적었다.)

2. 이제 before 값은 1이다. for문을 다시 수행하면, before != arr[ i ] 가 성립되지 않는다. 둘 다 1이기 때문이다.

 

3. DFS() 를 재호출하고, else 문을 다시 들어오면서 before는 0으로 초기화되고 위 과정을 수행하면 아래와 같다.

4. 위 과정들을 반복하여 결과를 출력한다.

public void DFS(int depth) {
    if(depth == M) {
        for(int x : graph) {
            sb.append(x + " ");
        }
        sb.append("\n");
    } else {
        int before = 0;
        for(int i=0; i<N; i++) {
            if(ch[i] == 1) {
                continue;
            } else if(before != arr[i]) {
                System.out.println("before : " + before);
                ch[i] = 1;
                graph[depth] = arr[i];
                before = arr[i];
                System.out.println("before2 : " + before);
                DFS(depth + 1);
                ch[i] = 0;
            }
        }
    }
}

 

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

• 해당 레벨에 대한 모든 경우를 탐색했으므로 다음 레벨로 넘어가기 위해 레벨을 더해준다.

7. ch[ ] 배열에 0을 넣어서 방문 여부를 초기화한다.

 

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

 

9. 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, ch;
	static StringBuilder sb = new StringBuilder();
	
	public void DFS(int depth) {
		if(depth == M) {
			for(int x : graph) {
				sb.append(x + " ");
			}
			sb.append("\n");
		} else {
			int before = 0;
			for(int i=0; i<N; i++) {
				if(ch[i] == 1) {
					continue;
				} else if(before != arr[i]) {
					ch[i] = 1;
					graph[depth] = arr[i];
					before = arr[i];
					DFS(depth + 1);
					ch[i] = 0;
				}
			}
		}
	}
	
	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];
		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);
		eit.DFS(0);
		System.out.println(sb);
	}
}