백준[15663] N과 M (9) (JAVA)

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

15663번: N과 M (9)

 

 

이 문제는 백트래킹 알고리즘을 공부하는 N과 M 시리즈의 문제중 하나이다.

 

오름차순으로 수열을 출력하는 점은 같지만 이문제의 특이한 점은 중복되는 수열을 출력하면 안된다는 점이다.

 

즉 수열이 중복되지 않게 백트래킹하는 과정에서 특수한 조건이 하나 필요하다.

 

이 문제를 풀기위한 아이디어는 우선 오름차순 정렬에 집중해보는것이다.

 

입력받는 숫자들을 오름차순으로 정렬한뒤

 

백트래킹을 시행한다. 

 

이때 그전에는 방문여부만 확인했다면 이전 숫자와 현재 숫자가 같은 숫자인지 확인해줘야 한다.

 

가령 입력되는 숫자가 4 4 2 , m = 2 인 경우

2 4

4 2

4 4

만 출력되어야 하고 그 과정을 살펴보면 다음과 같다.

 

첫번째 메소드 호출에서는 배열에 2를 저장후 현재 숫자를 2로 지정한다.

그리고 방문처리후 재귀호출을 시행한다.

 

다음은 배열에 숫자 4를 저장후 현재숫자를 4로 지정한다.

그리고 방문처리후 재귀호출을 시행한다.

 

이번엔 m 과 저장된수의 개수가 일치하므로 현재 수열을 저장후 리턴한다.

 

>> 2 4

 

현재 숫자가 4이고 반복문의 순회에 의해 다음숫자가 4 이므로 조건에 걸려

재귀호출은 일어나지 않고 반복문은 종료되고 이전 재귀호출 시점으로 돌아간다.

 

이 시점 역시 2만 저장되어있던 상황에서 역시 현재숫자가 4 이므로 반복문은 종료되고 이전 재귀 호출시점으로 돌아간다.

 

이제 현재 시점에서는 현재숫자가 2로 저장되어있고 반복문에 의해 4로 넘어가 현재 배열에 4를 저장후 

현재숫자를 4로 지정, 방문처리를 한뒤 다음 재귀호출로 진행된다.

 

새로 호출된 재귀함수에서는 현재숫자가 0으로 초기화 되어있으므로 처음으로 만나는 수인 2를 현재숫자로 지정후

현재숫자를 2로 지정, 방문처리를 한뒤 다음 재귀호출로 진행된다.

 

이번에는 m과 저장된수의 개수가 일치하므로 현재 수열을 저장후 리턴해준다.

 

>> 4 2

 

리턴된 시점에서는 현재숫자가 2로 지정되어있고 다음 순서인 4에 대해 저장후 재귀 호출을 해준다.

 

이번에는 m 과 저장된수의 개수가 일치하므로 현재 수열을 저장후 리턴한다.

 

>> 4 4

 

이제 모든 경우에 조건에 만족해 더 이상 재귀 호출이 일어나는 경우가 없으므로 각각의 반복문이 차례로 종료되며

백트래킹을 종료한다.

 

이제 코드로 구현해보자

 

일단 현재 수열을 저장해줄 메소드를 하나 만들어 주도록 하겠다.

 

	static void build() {
		for(int i = 0; i < m; i++) {
			sb.append(arr[i]).append(' ');
		}
		sb.append('\n');
	}

 

 

그리고 백트래킹으로 탐색할 메소드는 다음과 같이 정의해줄수 있다.

 

	static void dfs(int cnt) {
		if(cnt == m) {
			build();
			return;
		}
		
		int pre = 0;
		for(int i = 0; i < n; i++) {
			if(!visit[i] && pre != nums[i]) {
				visit[i] = true;
				pre = arr[cnt] = nums[i];
				dfs(cnt + 1);
				visit[i] = false;
			}
		}
	}

 

pre 변수를 지역변수로 두고 재귀호출시마다 초기화해주어야 한다.

 

앞서 설명한 예제 

3 2

4 4 2에 대한 실행 결과는 다음과 같이 잘 나오는것을 확인할 수 있다.

 

 

아래는 코드의 전문이다.

 

package boj3;

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

public class Boj15663 {
	
	static int n,m;
	static boolean[] visit;
	static int[] arr,nums;
	static StringBuilder sb = new StringBuilder();
	
	static void build() {
		for(int i = 0; i < m; i++) {
			sb.append(arr[i]).append(' ');
		}
		sb.append('\n');
	}
	
	static void dfs(int cnt) {
		if(cnt == m) {
			build();
			return;
		}
		
		int pre = 0;
		for(int i = 0; i < n; i++) {
			if(!visit[i] && pre != nums[i]) {
				visit[i] = true;
				pre = arr[cnt] = nums[i];
				dfs(cnt + 1);
				visit[i] = false;
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		visit = new boolean[n];
		arr = new int[m];
		nums = new int[n];
		
		st = new StringTokenizer(in.readLine()," ");
		for(int i = 0; i < n; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		in.close();
		
		Arrays.sort(nums);
		
		dfs(0);
		
		System.out.print(sb);
		
	}
}