문제

BOJ 15654: N과 M (5) https://www.acmicpc.net/problem/15654

조건 확인

• N개의 자연수 중에서 M개를 고른 수열을 출력한다.
• 중복되면 안된다.
• 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

• 입력받은 배열인 arr을 오름차순으로 정렬한 뒤 dfs 함수를 실행한다.
• dfs함수에 arr배열의 startIdx와 depth를 인자로 전달한다.
  • 자기 자신은 빼고 출력할 배열에 담아야 하므로 boolean 배열인 isVisited에 방문 처리인 true를 해주고 dfs 재귀 호출을 한 뒤 다시 false처리를 해준다.
  • 출력할 배열인 printArr에 depth값을 인덱스로 하여 arr[i]을 넣어준다.
  • dfs 재귀 호출을 할 때 startIdx에 i + 1을 넣어주고 depth 값에 depth + 1을 해준다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int N, M;
	static int[] arr;
	static int[] printArr;
	static boolean[] isVisited;
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		
		arr = new int[N]; // 입력받은 배열
		printArr = new int[N]; // 출력할 배열
		isVisited = new boolean[N];
		
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		sc.close();
		
		Arrays.sort(arr); // 오름차순으로 정렬했다.
		
		dfs(0, 0);
	}
	
	static void dfs(int startIdx, int depth) {
		if(depth == M) {
			for(int i=0; i<M; i++) {
				System.out.print(printArr[i]+" ");
			}
			System.out.println();
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(!isVisited[i]) {
				isVisited[i] = true; // 자기 자신은 빼고 배열에 담아야 함으로 boolean 배열을 추가해줬다.
				printArr[depth] = arr[i];
				dfs(i + 1, depth + 1);
				isVisited[i] = false;
			}
		}
		
	}
}

정리

• 자기 자신을 포함하지 않기 위해 boolean 배열을 통해 방문처리를 해주었다.