1861. 정사각형 방 (Java)

[SWEA] 1861. 정사각형 방

📝 풀이 과정

DFS(깊이 우선 탐색)를 사용해 주어진 맵에서 특정 위치에서 시작하여

숫자가 1씩 증가하는 연속된 방을 찾고
그중 가장 길게 이동할 수 있는 방의 수와 그 시작 방의 번호를 찾았다.

그리고 이동할 수 있는 방의 개수가 최대인 방이 여럿이라면
그 중에서 적힌 수가 가장 작은 것을 출력해야 하기에

처음 출발해야 하는 방 번호 = index
최대 방 이동 횟수 = maxRoom 

로 두고 DFS 탐색마다 갱신하도록 구현했다.

🧐 DFS 탐색 과정

예를 들어 다음과 같은 맵이 있다고 하자.

1 2 9
5 3 8
4 6 7

이 맵에서 (0, 0) 즉, 1 위치에서 시작하여 DFS를 수행한다고 가정하자.

1. 처음 DFS 호출
   (0, 0)에서 시작해 maxDepth는 1로 초기화된다.
   주변을 탐색해보면 (0, 1)로 이동할 수 있다. (map[0][1] = 2)

2. 두 번째 DFS 호출
   (0, 1)에서 DFS를 다시 호출하여 탐색을 진행한다.
   여기서도 maxDepth는 1로 초기화되지만, 주변에 이동할 수 있는 곳이 또 있으면 DFS를 호출하게 된다. (1, 1)로 이동할 수 있다. (map[1][1] = 3)

3. 연속된 DFS 호출과 깊이 갱신
   이 과정을 계속 반복하면서, 9에 도달할 때까지 이동하게 된다.
   이 경로의 최종 maxDepth = 9
   즉, (0, 0)에서 시작해서 9칸을 연속으로 이동할 수 있다.

maxDepth 는 DFS 탐색 중 현재 위치에서 출발해 도달할 수 있는
최대 깊이(이동할 수 있는 최대 칸 수)를 계산하여 최적의 경로를 찾는 데 사용한다.

👩🏻‍💻 제출 코드

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

public class Solution {

    static int N;
    static int[][] map;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

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

            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());
                }
            }

            int maxRoom = Integer.MIN_VALUE; // 최대 방 이동 횟수
            int index = -1; // 처음 출발해야 하는 방 번호
            for(int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    int result = dfs(i, j);
                    if(result > maxRoom){
                        maxRoom = result;
                        index = map[i][j];
                    } else if(result == maxRoom && map[i][j] < index) {
                        index = map[i][j];
                    }
                }
            }

            System.out.println("#" + t + " " + index + " " + maxRoom);
        }
    }

    private static int dfs(int x, int y) {
        int depth = 1;

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if(map[nx][ny] - map[x][y] == 1) {
                depth = Math.max(depth, 1 + dfs(nx, ny));
            }
        }

        return depth;
    }

}