백준 2468_안전영역_JAVA

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

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

public class Main {
    static int N, count, maxValue, maxCount;
    static int[][] grid;
    static boolean[][] visited;
    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));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        grid = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
                if (grid[i][j] > maxValue) {
                    maxValue = grid[i][j];
                }
            }
        }
        // 비를 0부터 가장큰 숫자까지 내리게 함
        for (int r = 0; r <= maxValue; r++) {
            int[][] newGrid = grid;
            count = 0;
            visited = new boolean[N][N];

            // 비에 인해 잠긴 곳은 0으로 표시
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (newGrid[i][j] <= r) {
                        newGrid[i][j] = 0;
                    }
                }
            }
            // 안전지역 구하는 중
            for (int k = 0; k < N; k++) {
                for (int l = 0; l < N; l++) {
                    if (newGrid[k][l] != 0 && !visited[k][l]) {
                        visited[k][l] = true;
                        dfs(newGrid, k, l);
                        count++;
                    }
                }
            }
            if (maxCount < count) maxCount = count;
        }

        System.out.print(maxCount);
    }

    private static void dfs(int[][] newGrid, int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny] && newGrid[nx][ny] != 0) {
                visited[nx][ny] = true;
                dfs(newGrid, nx, ny);
            }
        }
    }
}

 

 

회고

- 복잡했지만 하나하나 차근차근 풀어나가니까 풀렸다.

- 기본적인 dfs 문제들은 java로도 감을 잡은 것 같다