SEA1861_정사각형 방

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
 * dfs이지만 visited을 하면 오히려 꼬임, visited을 안해도 어차피 자신보다 작은 값은 안가니깐 상관없음
 * visited을 사용하면 새로운 숫자로 시작을 못할 때가 있음
 */
 
public class Solution {
 
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };
    static int cnt;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int test_case = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= test_case; tc++) {
 
            int N = Integer.parseInt(br.readLine().trim());
            int[][] map = new int[N][N];
 
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
 
            // max : 최대 이동한 방 , min_number : 최대로 이동한 방 중에서 출발방이 가장 작은 방
            int max = 1;
            int min_number = Integer.MAX_VALUE;
            // count : 각 방들의 번호를 인덱스로 하는 곳에 cnt를 넣어줌
            int[] count = new int[1000000];
            for (int i = 0; i < N; i++) {    
                for (int j = 0; j < N; j++) {
                    cnt = 0;
                    int number = map[i][j];
                    dfs(map, i, j, N, number);
                    cnt++;
                    count[number] = cnt;
                }
            }
            // 불필요하게 count배열 끝까지 검사할 필요 없게끔
            int M = N*N;
            for (int i = 0; i < M; i++) {
                // count배열 보면서 큰 값을 저장 그때의 인덱스를 저장
                if(max < count[i]) { // < , <= 의 차이!! count배열은 자동으로 sort해준 역할을 해준다
                    max = count[i];
                    min_number = i;
                }
            }
            System.out.println("#" + tc + " " + min_number + " " + max);
 
        } // end of tc
    } // end of main
 
    private static void dfs(int[][] map, int x, int y, int size, int number) {
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 범위안이고 이동할방번호가 현재보다 1클때만
            if (nx >= 0 && nx < size && ny >= 0 && ny < size && map[nx][ny] - number == 1) {
                cnt++;
                /*number = map[nx][ny];
                dfs(map, nx, ny, size, number);
                처음에는 이렇게 해줬었음 이렇게 하면
                1 3
                2 4 일때 1에서 2로 이동하고 다시 number = 1로 된상태로 다른곳을 탐색해야 되는데
                그게 안됨
                *******dfs로 다시 값줄때는 다른곳에서 사용하는 변수에 넣고 주지말고 바로 주자*******
                */
                dfs(map, nx, ny, size, map[nx][ny]);
            }
        }
    } // end of dfs
} // end of class