문제

문제 바로가기

풀이 코드

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

public class S1_2468 {
    static int n; // 2차원 배열의 가로 세로 길이
    static int[][] region;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static StringTokenizer st;
    static int max;
    static boolean[][] visited;
    static int count;
    static int answer = 1; // 아무 지역도 물에 안잠기면 전체 뭉덩이가 1개이기에 최소 1개는 무조건 나옴

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

        // 영역별 높이 넣어주고 최댓값 설정
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                region[i][j] = Integer.parseInt(st.nextToken());
                max = Math.max(region[i][j], max);
//                System.out.print(region[i][j]);
            }
//            System.out.println();
        }

        // 높이의 최댓값만큼 반복하면서 높이보다 큰 영역이고 방문 안한곳이면 dfs로 깊게 계속 연결되는 곳까지 방문체크
        for (int h = 1; h <= max; h++) {
            visited = new boolean[n][n];
            count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (region[i][j] > h && !visited[i][j]) {
                        count++;
                        dfs(i, j, h);
                    }
                }
            }
            answer = Math.max(answer, count);
        }
        System.out.println(answer);
    }

    static void dfs(int x, int y, int h) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if ((nx >= 0 && nx < n) && (ny >= 0 && ny < n) && !visited[nx][ny] && region[nx][ny] > h) {
                dfs(nx, ny, h);
            }
        }
    }
}

이 문제는 문제 이해를 하는데 너무 오래걸렸다.. 왜 도대체 안전영역이 5인가 4인가를 이해 못하다가 유튜브 영상을 봤는데 1분만에 이해가 되버렸다.
바로 코드를 작성해보니 dfs를 통해서 인접한 좌표가 범위내에 존재하고 물에 잠기지 않을 높이이면서 방문 여부를 확인해주면서 재귀로 계속 뻗어나가면서 방문체크만 해주면 된다.
전체 행열을 탐색하면서 높이를 1부터 최대 높이까지 계속해서 반복 탐색하면서 count를 세어주고 max count를 결과값으로 출력하면 된다.