SWEA 2105번
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

문제

---

생각하기

---

• 방향 탐색을 통한 DFS, 백트래킹 문제이다.

• 대각선탐색을 활용할 수 있는 문제이다.

동작

                    isVisited[i][j] = true;
                    isVisitedDesert[map[i][j]] = true;
                    DFS(i, j, i, j, 1, 0);
                    isVisitedDesert[map[i][j]] = false;
                    isVisited[i][j] = false;

백트래킹 문제이므로, 앞으로 나아갈 방향은 true를 해주고 다시 돌아왔을 때는 false값을 준다.

        for (int i = index; i < 4; i++) {
            int nowX = x + dirX[i];
            int nowY = y + dirY[i];

            // 시작한 곳으로 돌아오면 중지, 재귀 탈출 조건
            // counting이 3이상이고, counting이 짝수.
            if (startX == nowX && startY == nowY && counting >= 4) {
                maxResult = Math.max(maxResult, counting);
                return;
            }

            // 만약 i의 값으로 계속 이동할 수 있으면 계속해서 이동.
            if (rangeCheck(nowX, nowY) && !isVisited[nowX][nowY] && !isVisitedDesert[map[nowX][nowY]]) {

                isVisited[nowX][nowY] = true;
                isVisitedDesert[map[nowX][nowY]] = true;
                DFS(startX, startY, nowX, nowY, counting + 1, i);
                isVisitedDesert[map[nowX][nowY]] = false;
                isVisited[nowX][nowY] = false;
            }
        }

탐색을 하면서 답을 얻어내는 과정은 조건을 주면 된다.

출발한 곳을 방문할 수 있을 때 & 디저트 개수를 담은 counting변수가 4이상 일 때 모든 조건을 완수한 것이므로 결과값을 담을 maxResult와 최댓값 비교를 해서 결과를 얻으면 된다.

가지치기 조건은 단순한데, 배열을 벗어나지 않아야 하고, 이미 방문을 한 곳은 당연히 갈 필요가 없다

디저트가 겹치는 곳도 갈 필요가 없기 때문에, 현재 가지고 있는 디저트 여부를 isVisitedDesert를 통해서 체크한다
디저트의 숫자가 곧 index가 되어 해당 자리가 true일 경우 이미 가지고 있는 디저트로 간주하여 가지치기를 해줄 수 있다.

코드

---

Java

import java.util.*;
import java.io.*;

// 디저트를 가장 많이 먹을 수 있는 경우의 디저트 종류 수를 출력
// 디저트를 먹을 수 없는 경우 -1을 출력
// 탐색하는 방향에서 직사각형의 특징을 생각해야 됨 -> 직사각형의 특징. 마주보는 변의 길이가 같음
public class Solution {
    static int N;
    static int[][] map;
    static int[] dirX = {-1, 1, 1, -1}; // 대각선 방향으로 시계방향. (상우 -> 하우 -> 하좌 -> 상좌)
    static int[] dirY = {1, 1, -1, -1};
    static boolean[][] isVisited; // map의 경로상 방문여부를 체크하는 배열
    static boolean[] isVisitedDesert; // 방문한 디저트가 겹치는지 여부를 파악하기 위한 배열
    static int maxResult;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            sb.append('#').append(t).append(' ');

            N = Integer.parseInt(br.readLine());
            init(); // 변수 초기화

            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            // 완전탐색 & 백트래킹
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (i == 0 && (j == 0 || j == N - 1)) continue;
                    else if (i == N - 1 && (j == 0 || j == N - 1)) continue;

                    isVisited[i][j] = true;
                    isVisitedDesert[map[i][j]] = true;
                    DFS(i, j, i, j, 1, 0);
                    isVisitedDesert[map[i][j]] = false;
                    isVisited[i][j] = false;
                }
            }

            sb.append(maxResult).append('\n');
        }

        bw.write(sb.toString());
        bw.close();
    } // End of main

    private static void DFS(int startX, int startY, int x, int y, int counting, int index) {
        for (int i = index; i < 4; i++) {
            int nowX = x + dirX[i];
            int nowY = y + dirY[i];

            //  재귀 탈출 조건
            // counting이 4이상이고, 시작한 곳으로 돌아오면 중지,
            if (startX == nowX && startY == nowY && counting >= 4) {
                maxResult = Math.max(maxResult, counting);
                return;
            }

            // 만약 i의 값으로 계속 이동할 수 있으면 계속해서 이동.
            if (rangeCheck(nowX, nowY) && !isVisited[nowX][nowY] && !isVisitedDesert[map[nowX][nowY]]) {

                isVisited[nowX][nowY] = true;
                isVisitedDesert[map[nowX][nowY]] = true;

                // 만약 i의 값으로 계속 이동할 수 있으면 계속해서 이동.
                DFS(startX, startY, nowX, nowY, counting + 1, i);
                isVisitedDesert[map[nowX][nowY]] = false;
                isVisited[nowX][nowY] = false;
            }
        }

    } // End of DFS

    private static boolean rangeCheck(int nowX, int nowY) {
        return nowX >= 0 && nowX < N && nowY >= 0 && nowY < N;
    } // End of rangeCheck

    private static void init() { // 변수를 초기화 하는 메소드
        map = new int[N][N];
        isVisited = new boolean[N][N];
        isVisitedDesert = new boolean[101];
        maxResult = -1;
    } // End of init
} // End of Main class