사용한 알고리즘(백트래킹)
https://cobi-98.tistory.com/22
🔒 15649번 N과 M (1)
✔ 문제 설명
🚩 요구사항 분석
- 백트래킹을 이용하여 방문한 노드를 확인, 검사하기 위한 boolean 배열 생성
- 탐색 과정에서 값을 담을 int 배열 생성
🔑 문제풀이
자연수 N과 M을 정의하기위해 BufferedReader 을 사용하여 StringTokenizer로 값을 전역변수 지정하였다.
depth를 통해 재귀가 깊어질 때마다 (DMBackTracking함수) depth를 1씩 증가시켜
M과 같아지면 더이상 재귀를 호출하지 않고 탐색과정 중 값을 담았던 arr 배열을 출력해주고 return 해준다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
public static int N; // 자연수 N
public static int M; // 자연수 M
public static int[] arr;
public static boolean[] visit;
public 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());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[M];
visit = new boolean[N];
NMBackTracking(0);
System.out.println(sb);
}
public static void NMBackTracking(int depth){
if (depth == M){
for(int val : arr){
sb.append(val).append(' ');
}
sb.append('\n');
return;
}
for (int i = 0; i < N; i++) {
// 만약 해당 노드(값)을 방문하지 않았다면?
if (!visit[i]) {
visit[i] = true; // 해당 노드를 방문상태로 변경
arr[depth] = i + 1; // 해당 깊이를 index로 하여 i + 1 값 저장
NMBackTracking(depth + 1); // 다음 자식 노드 방문을 위해 depth 1 증가시키면서 재귀호출
// 자식노드 방문이 끝나고 돌아오면 방문노드를 방문하지 않은 상태로 변경
visit[i] = false;
}
}
}
}
'코딩테스트 > 백준' 카테고리의 다른 글
[백준 / Java] 15652번 N과 M (4) (0) | 2023.01.11 |
---|---|
[백준 / Java] 15651번 N과 M (3) (0) | 2023.01.11 |
[백준 / Java] 14888번 연산자 끼워넣기 (0) | 2023.01.11 |
[백준 / Java] 9663번 N-Queen (0) | 2023.01.11 |
[백준 / Java] 15650번 N과 M (2) (0) | 2023.01.11 |