반응형
이번에는 백준 15651번 문제를 통해 백트래킹 알고리즘 학습을 강화해 보자.
이쯤되면 점점 익숙해질 것이다.
문제 핵심
- 1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열
- 1 <= M <= N <= 7
- 중복하여 방문 가능
풀이 과정
이전 풀이를 보았다면 바로 생각이 날 수도 있다.
모든 경로가 중복 방문이 가능하다면? 다시 처음부터 시작하면 된다.
우리는 무조건 1부터 시작하는 조건을 가지고 있다. 그렇다면 변동하던 시작값을 고정시켜버리면 항상 중복하여 방문하게 된다.
핵심 코드
start 매개변수를 제외 시키고 반복문의 시작값을 0으로 고정하였다.
private static void backTracking(int depth, int M, int N) {
if (depth == M) {
for (int i : arr) {
stringBuilder.append(i).append(" ");
}
stringBuilder.append("\n");
return;
}
for (int i = 0; i < N; i++) {
arr[depth] = i + 1;
backTracking(depth + 1, M, N);
}
}
반복하여 진행하니 점점 한 눈에 알아볼 정도로 난이도가 내려가고 있다. ( 아니면 죄송...)
다음 4번째 N과 M을 끝으로 이해도를 높이길 바란다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int[] arr;
private static StringBuilder stringBuilder = new StringBuilder();
private static void backTracking(int depth, int M, int N) {
if (depth == M) {
for (int i : arr) {
stringBuilder.append(i).append(" ");
}
stringBuilder.append("\n");
return;
}
for (int i = 0; i < N; i++) {
arr[depth] = i + 1;
backTracking(depth + 1, M, N);
}
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken());
int M = Integer.parseInt(stringTokenizer.nextToken());
arr = new int[M];
backTracking(0, M, N);
System.out.println(stringBuilder);
}
}반응형
'백준 단계별 풀이' 카테고리의 다른 글
| [ 백준 2438번 문제 ] 별 찍기 - 1 - JAVA (1) | 2025.06.10 |
|---|---|
| [ 백준 15652번 문제 ] N과 M (4) - JAVA (1) | 2025.05.29 |
| [ 백준 15650번 문제 ] N과 M (2) - JAVA (1) | 2025.05.23 |
| [ 백준 24060번 문제 ] 알고리즘 수업 - 병합 정렬 1 - JAVA (2) | 2025.05.21 |
| [ 백준 4779번 문제 ] 칸토어 집합 - JAVA (0) | 2025.04.03 |