개요

조건이 많이 걸려있는 DFS 탐색 문제
탐색 문제의 대부분은 BFS로 풀어서 초반에 허우적 거렸다.
이 문제의 핵심은 주어진 조건들을 어떻게 처리하느냐에 있는 것 같다.
문제를 같이 보면서 해당 조건들을 어떻게 처리하는지를 잘 보고 이후에 비슷한 문제를 보았을때 조건 처리에 있어서 어려움이 없도록 해야한다.

문제분석

이런 형태로 디저트 카페가 널려있고. 우리는 대각선으로 밖에 이동을 할 수 없다.

일단, 일반적인 길의 형태가 아니고 대각선이라는 점에서 조금 위축이 될 수 밖에 없다.
그래도 대각선 정도야 이런식으로 구해서 이동해주면 된다

Point[] dir = {
        new Point(1,1), new Point(1,-1),
            new Point(-1,-1), new Point(-1,1)
    };

다만 여기서 주의해야 할 부분이 있다 방향좌표의 순서이다. 이것은 뒤의 조건을 서술하며 후술하겠다.

첫번째 조건은 대각선으로 이동하고 (앞에서 서술한 조건) , 사각형 모양을 그리며 출발한 카페로 돌아와야 한다는 조건이다.

사각형을 그린다는 조건에서 어떻게 사각형을 구성해야하는지 고민이 될 수 있다.
여기에서 자세히 생각해보면 사각형의 경우 방향을 바꾸는 횟수가 반드시 3번이 될 수 밖에 없다.
이걸 이용하여 방향전환을 할때마다 횟수를 세준 다음, 3번 이상이 되는 경우 사각형이 될 수 없기 때문에 해당 경우의 수는 세지 않도록 해야한다.

여기에서 앞서 말했던 방향좌표의 순서를 짚고 넘어가야한다. 나의 경우 사각형을 그릴때, 시계방향을 그리던 반시계 방향을 그리던 상관없이 사각형 이기 때문에, 회전 방향을 시계방향으로 정해주었다. 반시계방향을 해주던, 시계방향을 해주던 그건 작성자의 마음이다.

두번째 조건은 카페 투어 도중 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안된다는 것이다.

이 조건이 조금 까다롭게 느껴졌다. 처음에는 2차원 배열을 이용하여 visited 배열을 선언하려고 했는데 애매했다.. 그렇다면 set에 데이터를 넣고 중복이 없이 처리해볼까? 라고도 고민을 해보았지만. dfs로 처리하는데, 되돌아갈때 문제가 발생할 수 있지 않을까 싶어서 해당 부분도 기각을 했다.

최종적으로 생각한 방안은 제일 큰 수를 가지고 있는 디저트 카페의 값을 구한 다음. 해당 크기만큼의 디저트 카페 visited 배열을 생성하는 것이다.

이렇게 한다면,해당 번호에 해당하는 카페를 방문하면 이미 해당 번호를 방문했기 때문에 똑같은 번호의 카페를 방문할여지가 없게 된다.

나머지 조건은 간단하다.

하나의 카페에서만 디저트를 먹으면 안된다 -> depth가 1이면 안된다
같이 왔던 길을 다시 돌아가는 것도 안된다 -> 무조건 시계방향으로 돌도록 하는 것

이제 코드를 보자.

문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * 대각선 방향으로 움직이고,사각형 모양을 그리며 출발한 카페로 돌아와야 함
 * 같은 종류의 디저트를 다시 먹는 것을 싫어함 -> 같은 숫자의 디저트를 팔고있는 카페가 있으면 안됨
 * 하나의 카페에서 디저트를 먹는 것도 안됨
 * 같이 왔던 길을 되돌아 가는 것도 안됨
 * 디저트를 되도록 많이 먹으려고 한다
 * 사각형의 형태로 돌아와야한다
 * 사각형이면서 돌아와야 함
 * 1. 출발지점 = 도착지점
 * 2. 방향 전환 = 3번
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE&problemTitle=%EB%94%94%EC%A0%80%ED%8A%B8+%EC%B9%B4%ED%8E%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&&
 * @since 2023-11-02
 **/
public class Solution {
    static class Point{
        int x,y;
        int round; // 몇번을 꺾는지
        int curr; // 현재 방향
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Point(int x, int y, int round, int curr) {
            this.x = x;
            this.y = y;
            this.round = round;
            this.curr = curr;
        }
    }
    static int T,N;
    static int[][] map;
    static Point[] dir = {
        new Point(1,1), new Point(1,-1),
            new Point(-1,-1), new Point(-1,1)
    };
    //사각형을 시계방향으로 그리도록 유도함
    static int max;
    static boolean[] visited;
    static Point start;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());

        for(int t=1;t<T+1;t++){
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];
            int maxIdx = 0;

            for(int i=0;i<N;i++){
                st = new StringTokenizer(br.readLine()," ");
                for(int j=0;j<N;j++){
                    map[i][j] = Integer.parseInt(st.nextToken());
                    maxIdx = Math.max(maxIdx,map[i][j]);
                }
            }
            max = Integer.MIN_VALUE;
            visited = new boolean[maxIdx+1];
            //디저트 가게의 번호를 visited 배열로 구성함
            //중복이 나오지 않게 하기 위함

            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    start = new Point(i,j);
                    dfs(i,j,0,0);
                }
            }
            System.out.printf("#%d %d\n",t,max == Integer.MIN_VALUE ? -1 : max);
        }
    }
    static void dfs(int x,int y,int depth,int d){
        if(x < 0 || y < 0 || x >= N || y >= N) return;
        //유효하지 않은 좌표일 경우 리턴
        if(depth > 1 && x == start.x && y == start.y){
        // 하나의 가게만 들리지 않으면서
        // 출발했던 가게로 돌아온다 (사각형 조건 중 하나)
            max = Math.max(depth,max); // 가장 큰 depth를 update 
            return;
        }
        for(int i=d;i<=d+1;i++){
            //무조건 다음것
            //선택지가 현재방향으로 쭉 가거나, 그 다음 방향으로 틀거나 하나이다
            //그렇기 때문에 무조건 사각형을 그리도록 유도가 된다
            if(i> 3) break; // 사각형이 아닐 경우
            //방향을 트는 횟수가 3번 이상인 경우는 사각형이 될 수 없다
            int nx = x + dir[i].x;
            int ny = y + dir[i].y;

            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            
            if(visited[map[nx][ny]]) continue; // 이미 가본 디저트 가게일 경우
            visited[map[nx][ny]] = true;
            dfs(nx,ny,depth+1,i);
            visited[map[nx][ny]] = false;
        }
    }
}