import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] arr;
static boolean[] visit;
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());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
visit = new boolean[N];
arr = new int[M];
dfs(N,M,0);
System.out.println(sb);
}
static void dfs(int N, int M, int depth) {
if(M == depth) {
for(int num : arr) {
sb.append(num).append(" ");
}
sb.append("\n");
return;
}
for(int i = 0 ; i < N ; i++) {
if(!visit[i]) {
visit[i] = true;
arr[depth] = i + 1;
dfs(N,M,depth + 1);
visit[i] = false;
}
}
}
}
○ 문제 요약
1 ~ N까지 자연수를 M개 고른 수열을 출력해라.
○ 문제 풀이
이번에는 백트래킹이라는 알고리즘에 대해 알아보고 싶어서 이번 문제를 풀게 되었다. 일단 문제 풀이에 들어가기 전에 브루트 포스와 백트래킹의 차이에 대해 설명하고자 한다.
브루트 포스는 모든 경우의 수를 찾기 때문에 값을 100% 찾아낸다는 장점이 있다. 반대로 경우의 수가 많을수록 자원을 많이 필요로 한다.
백트래킹은 브루트 포스와 비슷하게 경우의 수를 찾지만 모든 경우의 수를 다 찾는 것은 아니다. 애초에 가능성이 있는 경우의 수만 찾기 때문에 경우의 수가 많아져도 브루트 포스보다 자원을 효율적으로 사용한다. 위에 코드를 보면 dfs라고 메서드를 만들어놓았다.
우리는 DFS를 이전 포스팅에서 한 번 해본 적 있다. 그러면 DFS와 백트래킹의 관계는 어떻게 되는 것일까?
DFS는 백트래킹의 방법 중 하나라고 보면 쉽게 관계를 정리할 수 있다. 여기서 DFS(깊이 우선 탐색)를 이용해 이 문제를 풀어보겠다.
static으로 int 배열의 arr과 boolean 배열의 visit를 메모리에 올려놓았다.
arr은 값을 저장하고 출력하기 위한 배열로서 역할을 하고 visit는 방문 여부를 확인해서 가능성을 알아보기 위한 역할을 하기 위해 선언해놓았다.
arr 배열의 크기는 뽑아내고 싶은 개수 즉, M개로 정했고 visit는 탐색할 자연수의 범위를 크기로 정했다.
dfs 메서드를 살펴보자. 변수는 N, M , depth로 3개를 받고 있다. N, M은 앞에서 설명했으니 지나가고 depth를 설명할 시점이다. depth의 역할은 M과 같으면 arr에 있는 값을 출력하도록 하고, 해당 값에 방문을 하지 않았으면 arr 배열에 값을 저장할 위치를 정해주는 인덱스 역할을 맡고 있다.
N = 4 , M = 2를 입력받았다고 가정하고 1 2를 출력하는 과정만 보도록 하자. 이것만 봐도 나머지는 충분히 예상할 수 있다.
1번 dfs메서드를 실행하면 M != depth 이기 때문에 if문을 지나서 for문으로 들어간다. for문에 들어가면 visit[0]은 아직 방문한 적이 없기 때문에 if문 조건에 부합해서 if문을 실행하여 다시 2번 dfs메서드를 호출하는 것을 알 수 있다. 이 과정을 i가 4보다 작을 때까지만 반복하면서 아래와 같이 값을 출력하는 것을 알 수 있다.
○ 결과
'문제풀이 > 백준' 카테고리의 다른 글
백준 19947. 투자의 귀재 배주형 (JAVA) (DP) (0) | 2022.04.02 |
---|---|
백준 11047. 동전 0 (JAVA) (0) | 2022.04.01 |
백준 9461. 파도반 수열(JAVA) (2) | 2022.03.29 |
백준 1003. 피보나치 함수(JAVA) (2) | 2022.03.28 |
백준 2231. 분해합 (JAVA) (2) | 2022.03.25 |