반응형
요즘 시험이니 일이니 핑계 거리가 생겨 포스팅이 많이 늦어졌습니다.
다시 매일 노력하여 포스팅 하도록 노력하겠습니다. 감사합니다.
이번에는 백준 15649번 문제를 통해 백트래킹 알고리즘을 실습해 보자.
백트래킹이란 간단히 설명하면
가능한 모든 경로 탐색 중 조건이 맞지 않으면 이전 단계로 돌아가 다시 탐색하는 알고리즘이다.
문제 핵심
- 1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열
- 1 <= M <= N < 8
풀이 과정
반복과 재귀를 통해 깊이에 따라 값을 처리한다.
dfs를 참고할 수 있겠다.
핵심 코드
- 현재 깊이를 체크한다.
- 최대 깊이에 도달한다면 리스트 값을 저장하고 리턴한다.
- 반복문을 통해 방문되지 않은 리스트 요소를 특정하여 방문한다.
- 리스트 현재 깊이 인덱스에 값을 저장한다.
- 재귀를 통해 다음 깊이로 이동한다.
- false를 통해 방문을 초기화 하고 이전으로 이동
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++) {
if(!visited[i]) {
visited[i] = true;
arr[depth] = i + 1;
backTracking(depth + 1, M, N);
visited[i] = false;
}
}
}EX) N : 4, M : 2
- N과 M이 위와 같을 때 1회전의 경우 다음과 같이 진행된다.
- 이후 depth + 1을 통해 M과 같아지게 되므로 저장 후 리턴된다.
- 마지막 방문했던 인덱스를 false를 통해 이전으로 돌아온다.
- 이 때 arr 배열에는 이후 값을 덮어쓰기 때문에 제거할 필요 없다.
다소 난해하지만, 재귀 방식을 이용한다면 풀 수 있는 문제이다.
이번 풀이에서는 DFS와 비슷하다고 볼 수 있다.
일정 깊이까지 도달한 후 다시 돌아오는 알고리즘으로
디버깅을 통해 로직이 진행되는 순서를 확인하면 좋겠다.
전체 코드
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 boolean [] visited;
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++) {
if(!visited[i]) {
visited[i] = true;
arr[depth] = i + 1;
backTracking(depth + 1, M, N);
visited[i] = false;
}
}
}
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());
arr = new int[M];
visited = new boolean[N];
backTracking(0, M, N);
System.out.println(stringBuilder);
}
}반응형
'백준 단계별 풀이' 카테고리의 다른 글
| [ 백준 24060번 문제 ] 알고리즘 수업 - 병합 정렬 1 - JAVA (2) | 2025.05.21 |
|---|---|
| [ 백준 4779번 문제 ] 칸토어 집합 - JAVA (0) | 2025.04.03 |
| [ 백준 26069번 문제 ] 붙임성 좋은 총총이 - JAVA (1) | 2025.03.12 |
| [ 백준 25192번 문제 ] 인사성 밝은 곰곰이 - JAVA (2) | 2025.03.09 |
| [ 백준 1010번 문제 ] 다리 놓기 - JAVA (2) | 2025.03.08 |