백준 19949번
https://www.acmicpc.net/problem/19949
for (int i = 1; i <= 5; i++) {
if (depth > 1) {
// depth가 2이상일 때, i로 들어가려는 값이 이전의 -1번째와 -2번째 자리와 같은지 검사해서 i값과 같으면 지나치도록 설정.
// 반복문 단계에서 미리 검사해서 가지치기를 해버림.
if (tempArr[depth - 1] == i && tempArr[depth - 2] == i) {
continue;
}
}
tempArr[depth] = i;
DFS(depth + 1);
}
1 ~ 5의 값을 넣으면 되므로 그냥 1부터 5까지의 반복문을 만들어서 10크기의 배열에 계속해서 넣어주면 된다.
depth
가 10이 되면 중지를 해서 점수를 채점하는 방식으로 했다.
여기서 가지치기는 문제에서 주어진 조건이 된다.
3문제 연속으로 같은 값이 들어갈 수 없으므로 depth
가 2이상일 때,
예를 들어 depth
가 3이 됬을 경우 이전의 2개 값과 i
값이 같은지 검사해서 2개의 값이 i
와 같을 경우 반복을 지나치도록 만들어주었다.
import java.util.*;
import java.io.*;
public class Main {
private static final int N = 10;
static int[] ansArr;
static int[] tempArr;
static int totalNumberOfCases;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ansArr = new int[N]; // 정답 배열
tempArr = new int[N]; // 경우의 수를 저장할 배열
totalNumberOfCases = 0; // 한가지 경우의 수 총점
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
ansArr[i] = Integer.parseInt(st.nextToken());
}
DFS(0);
System.out.println(totalNumberOfCases);
} // End of main
private static void DFS(int depth) {
if (depth == N) {
int correctCount = 0;
for (int i = 0; i < N; i++) {
if (ansArr[i] == tempArr[i]) {
correctCount++;
}
if (correctCount == 5) {
totalNumberOfCases++;
return;
}
}
return;
}
for (int i = 1; i <= 5; i++) {
if (depth > 1) {
// depth가 2이상일 때, i로 들어가려는 값이 이전의 -1번째와 -2번째 자리와 같은지 검사해서 i값과 같으면 지나치도록 설정.
// 반복문 단계에서 미리 검사해서 가지치기를 해버림.
if (tempArr[depth - 1] == i && tempArr[depth - 2] == i) {
continue;
}
}
tempArr[depth] = i;
DFS(depth + 1);
}
} // End of DFS
} // End of Main class