n과 m(9)

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

15663번: N과 M (9)

package 완전탐색_백트래킹;

import java.util.Arrays;
import java.util.Scanner;

public class bj_15663_N과M_9 {
	static int N,M,arr[],ans[];
	static boolean[] visit;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		arr=new int[N];
		ans=new int[M];
		visit=new boolean[N];
		for (int i = 0; i < N; i++) {
			arr[i]=sc.nextInt();
		}
		Arrays.sort(arr);
		soonten(0);
	}

	private static void soonten(int idx) {
		if (idx==M) {
			for (int i = 0; i < M; i++) {
				System.out.print(ans[i]+" ");
			}
			System.out.println();
			return;
		}
		for (int i = 0; i < N; i++) {
			if(visit[i]) continue;
			if(i>0&&arr[i]==arr[i-1]&&!visit[i-1]) continue;
			//만약 입력된 배열이 1,7,9,9라면
			//1,7/1,9/1,9가 나오지 않고 오른쪽 1,9는 나오지 않아야 하기 때문에
			//반복된 출력을 없애기 위해서 i가3일 때(9) i가 2의 값(9)과 같다면
			//출력을 하지 않게 건너뛰어 준다.
			//!visit[i-1]은 33번줄의 if(visit[i]) continue;가 자기랑 같은 값은 건너뛰어주고
			//앞 자리가 9일 때 arr[2]의 9와 arr[3]의 9가 나오지 않게 해줘야 하기 때문에
			//arr[2]의 값들을 출력할 때는 visit[2]의 값이 true이기 때문에 !visit[i-1]가 없다면
			//if 안에 i>0&&arr[i]==arr[i-1]의 조건 밖에 없기 때문에 9,9가 출력될 수 없다.
			//따라서 9,9도 나오게 해줄 수 있는 visit[i-1]값이 true일 때는 출력될 수 있게
			//값을 넣어줘야한다. 그리고 이제 앞에 값이 arr[3]의 9가 왔을 때
			//visit[2]는 false로 마쳤기 때문에 i=3일 때의 모든 값이 continue문으로 들어가기 때문에
			//앞자리 arr[3]의 9는 나올 수 없다.

			ans[idx]=arr[i];
			visit[i]=true;
			soonten(idx+1);
			visit[i]=false;
		}
	}
}

느낀점 : 재귀 문을 통해 만약 두자리가 주어진다면 앞에 값이 정해지고 두번째 값을 정해줄 때 앞에 값은 계속 true값으로 정해지고 뒤에 값들이 true가 됐다가 false로 바뀐다는 것을 이용하여 조건문에서 앞에 값이 false일 때는 건너뛰게 해줌으로써 앞자리와 뒷자리의 visit값들에 대한 이해가 많이 중요하고 재귀에 대해 조금 더 알 수 있었다,