백준 15650 N과 M (2) 자바 풀이

난이도 : 실버3

풀이일 : 2401232

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

15650번: N과 M (2)

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import java.util.Scanner;

public class Main {
	static boolean[] visited; // 중복 방문 방지
	static int[] array; // 수열 저장
	static int N;
	static int M;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		visited = new boolean[N];
		array = new int[M];
		
		DFS(0, 0);
	}
	
	static void DFS(int depth, int num) {
		// 수열이 채워졌으면 순서대로 출력
		if (depth == M) {
			for (int i : array) {
				System.out.print(i + " ");
			}
			System.out.println();
			return;
		}
		
		// 현재 번호 보다 큰 숫자들만 탐색
		for (int i = num; i < N; i++) {
			// 이전에 방문하지 않은 노드에 대하여
			if (!visited[i]) {
				visited[i] = true; // 방문 처리
				array[depth] = i + 1; // 수열 현재 깊이 자리에 i + 1 추가
				DFS(depth + 1, i); // 재귀 탐색
				visited[i] = false; // 자식 노드 탐색 후 방문 처리 초기화
			}
		}
	}
}

• visited : 중복 방문 방지를 위한 방문 여부 확인 배열
• array : 정답 수열을 저장할 배열
• DFS 탐색
  • 조건에 해당하는 수열을 오름 차순으로 출력하기 위해, 현재 숫자의 정보를 함께 인자로 받음
  • 만약 깊이가 수열의 길이와 같다면, 현재 수열에 있는 숫자들 순서대로 출력
  • 현재 숫자 이후의 숫자들에 대한 탐색 과정을 거침

---

느낀점

• 어제 풀이한 문제에서 오름차순이라는 조건만 추가된 문제였다. 해당 조건을 위해 DFS 함수의 인자를 하나 늘려줬다. 시리즈로 쭉 풀어보면 재미있을 것 같으니까 내일도 N과 M 시리즈 문제를 풀어봐야지.