백준 15654 N과 M (5) 자바 풀이

난이도 : 실버3

풀이일 : 2401313

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

15654번: N과 M (5)

---

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

---

풀이 코드

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

public class Main {
	static int N, M;
	static int[] nums;
	static int[] result;
	static boolean[] visited;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		nums = new int[N]; // 주어진 숫자 저장
		result = new int[M]; // 출력할 배열
		visited = new boolean[N];
		
		StringTokenizer num = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(num.nextToken());
		}

		// 주어진 숫자들 정렬
		Arrays.sort(nums);
		
		DFS(0);
		System.out.println(sb);
	}
	
	static void DFS(int depth) {
        	// 깊이 조건 만족 시 result 요소들 sb에 추가
		if (depth == M) {
			for (int i : result) {
				sb.append(i + " ");
			}
			sb.append('\n');
			return;
		}
        	// 방문하지 않은 숫자에 대해 방문 및 재귀호출
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				result[depth] = nums[i];
				DFS(depth+1);
				visited[i] = false;
			}
		}
	}
}

• 주어진 N개의 수를 저장할 nums 배열 선언 후, 숫자 담기
• Arrays.sort()로 nums 배열 정렬
• DFS 탐색
  • 현재 깊이가 출력할 배열의 길이와 같다면, 배열 내의 요소 StringBuilder에 추가 
  • 0부터 N 범위 내 방문하지 않은 수 번째 nums요소에 대해 방문
  • 방문 후 DFS 재귀 호출
  • 재귀 호출 후에는 해당 숫자 방문 초기화
• StringBuilder 내부 요소 출력

---

느낀점

• 기존의 N과 M 시리즈에서 숫자를 입력 받는 것과 정렬 하는 것이 추가된 문제였다. 이런 기본문제들 안풀고 여태 나는 자바로 무슨 문제들을 풀어온거지
• 여행 중에 자꾸 시간을 놓쳐서 프로젝트 커밋만 하게 된다. 시간을 정해두고 아침이나 밤이나 좀 고정적으로 문제를 풀고 포스팅해야지