백준 안전영역 2468 - java

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

2468번: 안전 영역

---

[문제 해결] 

• 해당 지역의 높이만큼 비가오면 해당 지역은 물에 잠긴다
• 주어진 지역들의 높이 만큼 비가 온다고 가정하고 bfs를 탐색하면 된다.
• 비가 와서 높이가 4이하인 지역이 모두 잠긴다면 안전 영역이 5가되고 높이가 6인만큼 비가오면 안정영역이 4가 된다.
• 이렇게 주어진 높이들 만큼 비가 온다고 가정하고 안전 영역의 최대 값을 구하면 된다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static ArrayList<ArrayList> list = new ArrayList<>();
    private static HashSet<Integer> set = new HashSet<>();
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int n;
    private static boolean visited[][];
    private static int dx[] = {0, 0, -1, 1};
    private static int dy[] = {-1 ,1, 0, 0};

    public static void main(String[] args) throws IOException {
        init();

        int max_safe = 1;
        int cnt = 0;
        for(var target : set) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(!visited[i][j] && (int)list.get(i).get(j) > target) {
                         bfs(new Location(i,j), target);
                         cnt++;
                    }
                }
            }
            visited = new boolean[n][n];
            max_safe = Math.max(max_safe, cnt);
            cnt = 0;
        }

        System.out.println(max_safe);
    }

    public static void bfs(Location start, int target){
        Queue<Location> q = new LinkedList<>();
        q.add(start);

        while(!q.isEmpty()) {
            Location cur = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(check(nx,ny,target)) continue;

                q.add(new Location(ny,nx));
                visited[ny][nx] = true;
            }
        }
    }

    public static boolean check(int nx, int ny, int target){
        return (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[ny][nx] || (int)list.get(ny).get(nx) <= target);
    }


    public static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        visited = new boolean[n][n];

        for(int i=0; i<n; i++) list.add(new ArrayList<>());

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                int height = Integer.parseInt(st.nextToken());
                list.get(i).add(height);
                set.add(height);
            }
        }
    }
}

class Location{
    int x;
    int y;

    public Location(int y, int x){this.y = y; this.x = x;}
}