1861. 정사각형 방(D4)

문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE

사실 이 문제는 Testcase가 약해서 사용한 방법대로 시작점을 정하지 않고

맵의 모든 점을 시작점으로 해도 시간 내에 정상적으로 동작하지만

1	2	3	4	5	6
12	11	10	9	8	7
13	14	15	16	17	18
24	23	22	21	20	19
25	26	27	28	29	30
36	35	34	33	32	31

만약 맵이 위와 같은 모양이라면 최대 200 * 200 사이즈에서 시간초과가 나게 된다.

1에서 dfs를 통해 36까지 확인하게 되고 2에서도 마찬가지, 3에서도, 4에서도 .... 의 과정을 거치게 되기 때문이다.

따라서 시작점을 정해주게 되면 주석으로 추가해놓은 내용처럼 시작점의 개수를 줄일 수 있고 그만큼

함수 호출 횟수를 줄일 수 있다.

---

- 소스 코드 -

import java.util.Scanner;
 
public class Solution1861 {
    static int dx[]= {0,0,1,-1};
    static int dy[]= {1,-1,0,0};
    static int map[][];
    static int count;
    static int dfs(int x,int y,int tempCount) {
        // 좌표를 받고 주변 4칸을 확인해서 다음으로 갈 칸이 있다면
        // 해당 칸으로 함수를 실행합니다.
        
        boolean flag=false;
        for(int i=0;i<4;i++) { // 주변 4칸을 확인해서
            if(map[x+dx[i]][y+dy[i]]==map[x][y]+1) { // 갈 수 있는 곳이 있다면
                flag=true;
                tempCount=dfs(x+dx[i],y+dy[i],tempCount)+1; // 해당 칸의 dfs 실행
            }
        }
        if(!flag) return 1; // 더이상 이동할 칸이 없으므로 1 반환
        else return tempCount; 
    }
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int T=scan.nextInt();
        for(int test_case=1;test_case<=T;test_case++) {
            int n=scan.nextInt();
            map=new int[n+2][n+2];
            count=1;
            for(int i=1;i<=n;i++) {
                for(int j=1;j<=n;j++) {
                    map[i][j]=scan.nextInt();
                }
            }
            int resultX=0;
            int resultY=0;
            for(int i=1;i<=n;i++) {
                for(int j=1;j<=n;j++) {
                    boolean plusCheck=false;
                    boolean minusCheck=true;
                    for(int k=0;k<4;k++) { // 주변 4칸을 확인해서
                        /////////// (1) 자신보다 1 큰 칸이 있고 ///////////
                        if(map[i+dx[k]][j+dy[k]]==map[i][j]+1) plusCheck=true;
                        /////////// (2) 자신보다 1 작은 칸이 없다면 시작점으로 한다. ///////////
                        if(map[i+dx[k]][j+dy[k]]!=0&& // 0인경우는 벽이므로 제외
                                map[i+dx[k]][j+dy[k]]==map[i][j]-1) minusCheck=false;
                    }
                    
                    //////////// 시작점 개수 변화 ///////////
                    // size 200짜리 테스트케이스 (전체 시작점으로 할 시 40000개)
                    // (1) 조건 거칠 경우 : 40000 -> 39852
                    // (2) 조건 거칠 경우 : 39852 -> 148
                    
                    if(plusCheck && minusCheck) {
                        int temp=dfs(i,j,0);
                        if(temp>count) {
                            // 만약 새로운 시작점에 대해 dfs값이 더 크다면 갱신
                            resultX=i;
                            resultY=j;
                            count=temp;
                        }else if(temp==count) {
                            // dfs값이 같다면 해당 칸의 값을 비교하여 더 작은 값으로 갱신
                            if(map[resultX][resultY]>map[i][j]) {
                                resultX=i;
                                resultY=j;
                            }
                        }
                    }
                }
            }
            System.out.printf("#%d %d %d\n",test_case,map[resultX][resultY],count);
        }
        scan.close();
    }
}