백준 19949번
https://www.acmicpc.net/problem/19949

문제

---

생각하기

---

• 백트래킹과 부르트포스를 사용하는 문제이다.
  • isVisited를 사용하여 방문여부를 따질 필요가 없다
    • 그냥 배열자리에 1 ~ 5의 값을 넣어주면 됨

• 중복이 일어나지 않도록 가지치지 조건이 필요하다
  • 3문제 연속으로 같은 값이 들어가지 않게 가지치기 조건이 필요하다.

동작

        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와 같을 경우 반복을 지나치도록 만들어주었다.

코드

---

Java

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