[SWEA/Java] 정사각형 방(1861)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc

SW Expert Academy

1. 문제 분석

문제 개요:
주어진 N x N 크기의 방에서 각 방에 있는 숫자들을 이동시켜서 가장 긴 연속된 숫자 시퀀스를 찾는 문제입니다. 각 숫자는 방의 상하좌우로 이동할 수 있으며, 이동 가능한 숫자들 중 가장 긴 연속된 숫자 시퀀스의 시작 숫자와 길이를 구해야 합니다.

입력 형식:

1. 첫 줄에 테스트 케이스의 수 T가 주어진다.
2. 각 테스트 케이스는 다음과 같은 형식이다:
   • 첫 줄에 보드의 크기 N이 주어진다.
   • 다음 N줄에 보드의 상태가 주어진다. 각 줄은 N개의 정수로 구성된다.

출력 형식:

• 각 테스트 케이스에 대해, 가장 긴 연속된 숫자 시퀀스의 시작 숫자와 길이를 출력한다.

2. 알고리즘 종류

해당 문제는 "깊이 우선 탐색(DFS)" 알고리즘을 사용하여 해결할 수 있습니다. 각 방의 숫자에서 시작하여 인접한 방의 숫자들을 재귀적으로 탐색하여 가장 긴 연속된 숫자 시퀀스를 찾습니다. 이때, 이미 방문한 방을 다시 방문하지 않도록 해야 합니다.

3. 주요 부분 및 코드 작성 방법

1. 탐색 처리:

• 각 방의 숫자에서 시작하여 상하좌우로 인접한 방의 숫자를 탐색합니다.
• 현재 방의 숫자보다 1이 더 큰 숫자가 인접하면, 그 방으로 이동하여 탐색을 계속합니다.
• 가장 긴 연속된 숫자 시퀀스를 찾아서 기록합니다.

2. search() 메서드:

• 재귀적으로 상하좌우 방으로 이동하며 숫자 시퀀스를 찾습니다.
• 이동할 수 있는 방이 없거나, 이동 가능한 숫자가 없는 경우 현재 시퀀스의 길이를 반환합니다.

3. main() 메서드:

• 입력을 읽어와서 방의 상태를 설정합니다.
• 각 방에서 search() 메서드를 호출하여 가장 긴 연속된 숫자 시퀀스를 찾습니다.
• 결과를 출력합니다.

4. 코드 설명

DFS 탐색 (search()):

java코드 복사
public static void search(int x, int y) {
    for(int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];

        if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
        if(room[nx][ny] == room[x][y] + 1) {
            cnt++;
            search(nx, ny);
        }
        if(max < cnt) {
            max = cnt;
        }
    }
}

• dx와 dy 배열을 사용하여 상하좌우로 이동합니다.
• 현재 방의 숫자보다 1이 더 큰 숫자가 있는 방으로 이동하여 재귀적으로 탐색합니다.
• 탐색 후 최대 시퀀스 길이를 업데이트합니다.

5. 전체 코드

java코드 복사
package SWEA1861_240822;

import java.io.*;
import java.util.*;

public class Solution {
    static int N, max, start = 0, cnt;
    static int[][] room;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

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

            for(int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for(int j = 0; j < N; j++) {
                    room[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int[] result = new int[N * N + 1];
            int resultMax = 0;
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    cnt = 1;
                    max = 0;
                    search(i, j);
                    result[room[i][j]] = max;
                    if(resultMax < max) resultMax = max;
                }
            }

            for(int i = 0; i < result.length; i++) {
                if(result[i] == resultMax) {
                    System.out.println("#" + tc + " " + i + " " + resultMax);
                    break;
                }
            }
        }
    }

    public static void search(int x, int y) {
        for(int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if(room[nx][ny] == room[x][y] + 1) {
                cnt++;
                search(nx, ny);
            }
            if(max < cnt) {
                max = cnt;
            }
        }
    }
}

• main() 메서드에서 각 테스트 케이스를 처리하고, 방의 상태를 설정하여 결과를 출력합니다.
• search() 메서드에서 DFS를 이용해 숫자 시퀀스를 찾습니다.