SWEA 1861 - 정사각형 방 [Java]

문제

SW Expert Academy

풀이

처음에는 아무 생각 없이 DFS로 풀었는데 틀렸다. n보다 n+1을 먼저 방문하는 경우를 고려해야 한다.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Scanner;
 
public class Solution {
     
    private static final int[] dx = {1, 0, -1, 0};
    private static final int[] dy = {0, 1, 0, -1};
    private static int N;
    private static int[][] A;
    private static HashMap<Integer, String> map;
    private static Deque<Integer> stack;
    private static boolean[][] visited;
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            A = new int[N][N];
            map = new HashMap<>();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    A[i][j] = sc.nextInt();
                    map.put(A[i][j], (i + "," + j));
                }
            }
             
            visited = new boolean[N][N];
            int[] res = new int[N*N + 1];
             
            for (int n = 1; n <= N*N; n++) {
                String[] ij = map.get(n).split(",");
                int i = Integer.parseInt(ij[0]);
                int j = Integer.parseInt(ij[1]);
                if (!visited[i][j]) {
                    stack = new ArrayDeque<>();
                    dfs(i, j);
                     
                    int cnt = stack.size();
                    while (!stack.isEmpty()) {
                        res[stack.poll()] = cnt--;
                    }
                }
            }
             
            int maxVal = Integer.MIN_VALUE;
            int answer = 0;
             
            for (int i = 1; i < res.length; i++) {
                if (res[i] > maxVal) {
                    maxVal = res[i];
                    answer = i;
                }
            }
             
            System.out.println("#" + tc + " " + answer + " " + maxVal);
        }
         
        sc.close();
    }
     
    private static void dfs(int x, int y) {
        visited[x][y] = true;
        stack.add(A[x][y]);
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (isValid(nx) && isValid(ny) && !visited[nx][ny] && A[nx][ny] == A[x][y] + 1) {
                dfs(nx, ny);
            }
        }
    }
     
    private static boolean isValid(int x) {
        return 0 <= x && x < N;
    }
}