백준 15649 N과 M(1) 자바 풀이

난이도 : 실버3

풀이일 : 2401221

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

15649번: N과 M (1)

---

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

---

풀이 코드

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);
	}
	
	static void DFS(int depth) {
		// depth가 M과 같다면, 수열 내부 수 순서대로 출력
		if (depth == M) {
			for (int i : array) {
				System.out.print(i+ " ");
			}
			System.out.println();
			return;
		}
		
		for (int i = 0; i < N; i++) {
			// 이전에 방문하지 않았던 노드에 대하여
			if (!visited[i]) {
				visited[i] = true; // 방문 체크
				array[depth] = i + 1; // 현재 깊이에 해당 수 추가
				DFS(depth + 1); // 깊이를 1 추가 후 DFS 탐색 
				visited[i] = false; // 방문 체크 되돌리기 
			}
		}
	}
}

• visited : DFS 탐색에서 중복 방문을 방지하기 위한 방문 확인 boolean 배열
• array : 수열에 들어갈 수를 담을 배열
• 주어진 수 N길이 만큼의 visited 배열 생성
• 수열의 길이 M 길이 만큼의 array 배열 생성
• DFS 실행
  • depth가 M과 같다면, 현재 수열에 담긴 숫자들 모두 출력 후 줄바꿈
  • 0부터 N까지 순회하며 이전에 방문하지 않았던 노드에 대해
    • visited 배열에서의 방문 체크,
    • array 배열에서 현재 깊이에 해당 수 추가
    • 깊이를 1 더해 DFS 재귀탐색
    • 자식노드를 탐색하고 돌아올 시, visited 배열에서 방문 체크를 풀어주기

---

느낀점

• 파이썬으로 푸는 골드 난이도 알고리즘들은 보통 이미 아는 알고리즘이고, 자바로 푸는 실버 난이도 알고리즘들은 모르는 알고리즘들이어서 자바로 문제푸는게 훨씬 어렵게 느껴진다. 어쩌면 자바로 골드 아는거 푸는 게 덜 어려울지도 자료형을 좀 공부하면
• 자바로는 파이썬 알고리즘 풀 때 놓치고 지나갔던 알고리즘들을 공부한다고 생각하고 차근차근 넓은 범위의 문제들을 풀어봐야지.