[DFS완탐]SWEA_디저트카페

먼저, 대각선으로 이동하는 참신한 문제였다. 사실 대각선으로 이동하는 거 자체는 어렵지 않았다.

예외처리랑 여러가지 상황이 생각보다 까다로웠다.

처음에는 BFS로 생각하고 코딩을 하였는데 결과를 보니까 동시에 인접한 곳을 탐색하기 때문에 처음위치로

돌아올 수 없었다. --> 미리 map을 구현해서 결과를 생각해보자....

그래서 DFS(깊이탐색)으로 해야겠다고 생각을 했고 구현하기가 쉽지 않았다(stack,재귀)

재귀로 구현(++,--과정 중요!!)을 하여야 겠다고 생각했고, 처음위치도 알고있어야하고, 먹은 디저트 이미 지나온 길을 모두 표시하여야 하고 시간초과 오류와 여러가지 예외상황이 있었다. 시작점으로 돌아오는 과정중에 사각형이 아니어도 돌아올 수 있는 case를 발견하였고, 사각형이 되기위해서는 방향전환이 3번만 이루어져야한다는것을 깨달았다.

이런 시뮬레이션 상황( 예외처리 상황을 ) 찾아내는 것이 어려웠고, 이것을 문제를 읽으면서 미리 파악하는 연습을

최대한 해야겠다고 생각했다. 정 안되면 코딩하다가 발견하겠지만, 처음부터 미리 생각해보는 습관을 길러야한다.

--> dfs재귀를 통한 여러가지 탐색을 구현하면서 , 예외사항을 발견하고 처리하는것이 관건인것 같다.

 

[문제]

친구들과 디저트 카페 투어를 할 계획이다.

[Fig. 1]과 같이 한 변의 길이가 N인 정사각형 모양을 가진 지역에 디저트 카페가 모여 있다.
 

원 안의 숫자는 해당 디저트 카페에서 팔고 있는 디저트의 종류를 의미하고

카페들 사이에는 대각선 방향으로 움직일 수 있는 길들이 있다.

디저트 카페 투어는 어느 한 카페에서 출발하여

[Fig. 2]와 같이 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.
 
 

디저트 카페 투어를 하는 도중 해당 지역을 벗어나면 안 된다.

또한, 친구들은 같은 종류의 디저트를 다시 먹는 것을 싫어한다.

즉, [Fig. 3]과 같이 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다.
 
 

[Fig. 4]와 같이 하나의 카페에서 디저트를 먹는 것도 안 된다.

 

[Fig. 5]와 같이 왔던 길을 다시 돌아가는 것도 안 된다.
 

 

친구들과 디저트를 되도록 많이 먹으려고 한다.

디저트 가게가 모여있는 지역의 한 변의 길이 N과 디저트 카페의 디저트 종류가 입력으로 주어질 때,

임의의 한 카페에서 출발하여 대각선 방향으로 움직이고

서로 다른 디저트를 먹으면서 사각형 모양을 그리며 다시 출발점으로 돌아오는 경우,

디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 정답으로 출력하는 프로그램을 작성하라.

만약, 디저트를 먹을 수 없는 경우 -1을 출력한다.


[예시]

한 변의 길이 N이 4인 지역에 디저트 카페가 [Fig. 6]과 같이 있다고 생각하자.
 

디저트 카페 투어가 가능한 경우는 [Fig. 7]과 같이 5가지로 나눌 수 있다.

(출발한 곳과 도는 방향은 다를 수 있지만, 디저트 카페 투어의 경로가 그리는 사각형 모양은 5가지 중 하나이다.)

 

[Fig. 7]

 
이 중에 디저트를 가장 많이 먹을 수 있는 경우는 ⑤인 경우로 디저트의 종류는 6개이다.

따라서, 정답은 6이 된다.


[제약사항]

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초

2. 디저트 카페가 모여있는 지역의 한 변의 길이 N은 4 이상 20 이하의 정수이다. (4 ≤ N ≤ 20)

3. 디저트 종류를 나타나는 수는 1 이상 100 이하의 정수이다.


[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 디저트 카페가 모여있는 지역의 한 변의 길이 N이 주어진다.

그 다음 N 줄에는 N * N 크기의 디저트 카페에서 팔고 있는 디저트 종류에 대한 정보가 주어진다.


[출력]

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 가능한 경우 중 디저트를 가장 많이 먹을 때의 디저트 수 이다.

만약, 디저트를 먹을 수 없는 경우 정답은 -1이다.

 

 

 

import java.util.Scanner;
 
public class Main {
    
    static int[][] map;
    static int[][] road; //지나온 길을 표시하기 위해
    static int N;
    static int[] Eat; //먹은 디저트를 두번먹지 않기위해 
    static int start_x=-1,start_y=-1; //처음위치를 기억하기 위해 설정.
    static int[] dx = {-1,-1,1,1}; //좌상(-1,1), 우상(1,1), 좌하(-1,-1), 우하(1,-1)
    static int[] dy = {-1,1,-1,1}; //clockwisw
    static int max = -1; //없는 경우 -1 로 한다.
    
    public static boolean InRange(int x,int y) {
        if(x < 0 || y < 0 || x >= N || y>=N ) return false;
        else return true;
    }
    
    public static void dfs(int len,int x,int y,int t,int d) { //방향전환 3번만 해야됨. t는 0번 방향전환 d는 방향 번호
        if(start_x == x && start_y==y && len !=2 && t==4) { 
            max = len >= max ? len : max;
            return; //처음점으로 돌아온경우. 길이가 2 이면 가자마자 돌아오는 경우이고 방향전환이 (3+1)번 이루어 져야한다.
        }else if(start_x == x && start_y ==y && len==2) return; //바로 돌아온경우는 return해준다
        if(t>4) return; //방향전환 5번부터는 return; 이미 사각형이 아니다.
        if(len==0) { // 처음시작일때 시작점을 저장해준다.
            start_x = x;
            start_y = y;
        }
        //좌상
        if(InRange(x+dx[0],y+dy[0])&&Eat[map[x+dx[0]][y+dy[0]]]!=1 && road[x+dx[0]][y+dy[0]]!=1) { // 먹지도 않은 디저트에 가지도 않은 길일때.
            Eat[map[x+dx[0]][y+dy[0]]]=1;
            road[x+dx[0]][y+dy[0]]=1;
            if(d!=0) { //전화 방향이 다르면
                t++;
            } //dfs전까지는 ++ 해준다
            dfs(len+1,x+dx[0],y+dy[0],t,0);
            if(d!=0)t--; //dfs해준후 다시 다음 dfs를 위해 --해준다.
            Eat[map[x+dx[0]][y+dy[0]]]=0;
            road[x+dx[0]][y+dy[0]]=0;
        }//우상
        if(InRange(x+dx[1],y+dy[1])&&Eat[map[x+dx[1]][y+dy[1]]]!=1 && road[x+dx[1]][y+dy[1]]!=1) {
            Eat[map[x+dx[1]][y+dy[1]]]=1;
            road[x+dx[1]][y+dy[1]]=1;
            if(d!=1) t++;
            dfs(len+1,x+dx[1],y+dy[1],t,1);
            if(d!=1)t--;
            Eat[map[x+dx[1]][y+dy[1]]]=0;
            road[x+dx[1]][y+dy[1]]=0;
        }//좌하
        if(InRange(x+dx[2],y+dy[2])&&Eat[map[x+dx[2]][y+dy[2]]]!=1 && road[x+dx[2]][y+dy[2]]!=1) {
            Eat[map[x+dx[2]][y+dy[2]]]=1;
            road[x+dx[2]][y+dy[2]]=1;
            if(d!=2) t++;
            dfs(len+1,x+dx[2],y+dy[2],t,2);
            if(d!=2)t--;
            Eat[map[x+dx[2]][y+dy[2]]]=0;
            road[x+dx[2]][y+dy[2]]=0;
        }//우하
        if(InRange(x+dx[3],y+dy[3])&&Eat[map[x+dx[3]][y+dy[3]]]!=1 && road[x+dx[3]][y+dy[3]]!=1) {
            Eat[map[x+dx[3]][y+dy[3]]]=1;
            road[x+dx[3]][y+dy[3]]=1;
            if(d!=3) t++;
            dfs(len+1,x+dx[3],y+dy[3],t,3);
            if(d!=3)t--;
            Eat[map[x+dx[3]][y+dy[3]]]=0;
            road[x+dx[3]][y+dy[3]]=0;
        }
        
    }
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int Total = sc.nextInt();
        for(int i=1;i<=Total;i++) {
            N = sc.nextInt();
            map = new int[N][N];
            road = new int[N][N];
            Eat = new int[101]; //1~100까지의 디저트 종류 존재
            
            for(int m=0;m<N;m++) {
                for(int p = 0;p<N;p++) map[m][p]=sc.nextInt();
            }//input the map
            for(int m=0;m<N;m++) {
                for(int j=0;j<N;j++) {
                    if(m==0 && j==0) continue;
                    if(m==0 && j==N-1) continue;
                    if(m==N-1 && j==0) continue;
                    if(m==N-1 && j==N-1) continue; //예외처리 절대 가능성이 없는점 제외
                    start_x=-1;
                    start_y=-1; // for문마다 시작점을 초기화해준다.
                    Eat[map[m][j]]=2; //시작점으로 돌아올 수 있게 해주기위해 시작점은 특별하게 2로 표시해준다.
                    road[m][j]=2;
                    dfs(0,m,j,0,-1); //m,j 부터 시작해서 dfs 탐색 시작. 0번전환 -1방향부터 시작
                    Eat[map[m][j]]=0; //다음 for문을 실행하기위해 초기화해준다.
                    road[m][j]=0;
                }
            }
            System.out.println("#"+i+" "+max);
            max=-1;
        }
    }
}