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

문제

SW Expert Academy

 

풀이

0. 문제 해석

최대 몇개의 방을 이동 할수 있는지 체크하기 위하여

방마다 최대 몇 개 까지 이동할 수 있는지 델타방식으로 dfs를 통해 확인하여 최댓값을 탐색하고,

그 최댓값중에 가장 큰 값의 방 번호를 출력하면 된다.

 

1. 방 번호 입력하기

방 정보를 입력해주고 델타를 이용해 상하좌우 이동할 것이므로 편하게 사방 테두리를 0 처리해주었다.

 

2. DFS

모든 점에 대해 DFS를 진행해준다.

 

이동할 수 있는 점일 때 깊이를 체크하기 위한 count, 처음 시작점을 기록하기 위한 start를 사용한다.

점 마다 가장 많이 갈 수 있는 방 수를 startMax 배열에 저장한다.

 

3. 최댓값 찾기

최댓값이 여러개라면 숫자가 낮은 수부터 출력해야 하므로

뒤부터 하나씩 비교하여 가장 큰 시작점을 찾아준다.

 

4. 전체 코드

// [SWEA] 1861. 정사각형 방 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int n; 
    static int max; // 최대 이동할 수 있는 방
    static int maxNum; // 최대 일때 인덱스
    static int[][] arr; // 방 배열 
    static int[] startMax; // 시작점에서 갈 수 있는 최대 방수 기록
    // 상하좌우
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static StringTokenizer st;
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int t = Integer.parseInt(br.readLine());
        
        for(int x = 1; x <= t; x++) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n+2][n+2]; // 인덱스부터 시작하여 외곽 0 처리하기 위해 n+2
            startMax = new int[n * n + 1]; 
             
            for(int i = 1; i <= n; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j = 1; j <= n; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
             
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    dfs(i,j,1,arr[i][j]);
                }
            }           
            max = 0;
            maxNum = 0;
            // 방의 개수가 최대인 시작점 찾기 (여럿이라면 적힌 수가 가장 작은 것)
            for(int i = startMax.length - 1; i > 0 ; i--) {
                if(startMax[i] >= max) {
                    max = startMax[i];
                    maxNum = i;
                }
            }
            System.out.println("#" + x + " " + maxNum + " " + max);
        }
    }
     
    public static void dfs(int x,int y,int count, int start) {
        int cur = arr[x][y];
 
        for(int i = 0; i < 4; i++) {
            int next = arr[x + dx[i]][y + dy[i]];
            // 외곽이 아니고 차이가 1이라면
            if(next != 0 && next - cur == 1) {
                dfs(x + dx[i], y + dy[i], count + 1, start);
            }
        }
         
        // start 에서 갈 수 있는 최대 방 수
        if(count > startMax[start]) {
            startMax[start] = count;
        }
    }
}