[백준 2468번] 안전 영역 :: 늦깎이 IT

[백준 2468번] 안전 영역 URL

1. 비가 내리지 않을 경우, 안전지대는 1로 초기화한다.

2. 비는 안전지대의 최대 높이만큼만 내리면 된다. 최대 높이보다 비가 더 많이 내릴 경우는 어차피 안전지대는 0이

되기 때문이다.

3. 비를 1씩 내릴때마다 Map의 값을 -1 해주며, BFS탐색을 하고 최대 값을 찾는다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, ans;
    static int[][] map;
    static int maxVal;
 
    static int[] dirX = new int[] { 0, 0, 1, -1 };
    static int[] dirY = new int[] { 1, -1, 0, 0 };
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        map = new int[N][N];
        maxVal = 0;
        ans = 1;
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                maxVal = Math.max(maxVal, map[i][j]);
            }
        }
        solve();
        System.out.println(ans);
    }
 
    public static void solve() {
 
        for (int rain = 1; rain <= maxVal; rain++) {
 
            sink();
            boolean[][] visited = new boolean[N][N];
 
            int count = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && map[i][j] > 0) {
                        bfs(i, j, visited);
                        count += 1;
                    }
                }
            }
            ans = Math.max(ans, count);
        }
    }
 
    public static void bfs(int row, int col, boolean[][] visited) {
 
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(row, col));
        visited[row][col] = true;
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
 
            for (int i = 0; i < 4; i++) {
 
                int nr = node.row + dirX[i];
                int nc = node.col + dirY[i];
 
                if (isBoundary(nr, nc) && !visited[nr][nc] && map[nr][nc] > 0) {
                    visited[nr][nc] = true;
                    q.offer(new Node(nr, nc));
                }
            }
        }
    }
 
    public static void sink() {
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] -= 1;
            }
        }
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
}
 
class Node {
    int row;
    int col;
 
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
 
}