우주수첩의 우주먼지

시간 초과package BKD_0x0C_BackTracking;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_15651 { static int N; static int M; static int[] arr; static void dfs(int depth){ if(depth==M){ for(int val : arr){ System.out.print(val + " "); } System.ou..

https://www.acmicpc.net/problem/15650package BKD_0x0C_BackTracking;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_15650 { static int N; static int M; static int[] arr; static void dfs(int at, int depth){ if(depth == M){ for(int val : arr){ System.out.print(val..

백트래킹이란?- 노드의 유망성을 판단한 뒤 해당 노드가 유망하지 않다면 부모노드로 돌아가 다른 자식 노드를 찾는 방법.❗️즉, 모든 경우의 수를 찾아 보지만 그 중에서도 가능성 있는 경우의 수만 찾아보는 것을 의미❗️  백트래킹 vs dfs vs 브루트포스 1. 브루트 포스- 모든 경우의 수를 찾아본다.- 장점 : 만족하는 값을 100% 찾아냄- 단점 : 조합 가능 경우의 수에 따라 필요 자원 크기가 커 질 수 있음. 2. 백트래킹 - 해당 범위 내에서 조건을 추가하여 값의 유망성을 판단.- 장점 : 탐색에 불필요한 자원을 줄일 수 있다. (브루트 포스의 단점 보완) 3. dfs - 백트래킹에 사용되는 대표적인 탐색 알고리즘❗️ 백트래킹의 방법 중 하나가 dfs임 ❗️

https://www.acmicpc.net/problem/15649 package BKD_0x0C_BackTracking;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_15649 { // 1부터 N까지의 자연수 중에서 중복 없이 M개를 고르는 수열 static int N; static int M; static boolean[] visit = new boolean[N]; // 재귀를 진행하면서 이미 방문한 노드라면 다음 노드를 탐색하도록 하기 위함. == 유만한 노드인지 검사 ..