2468번 : 안전 영역 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(25분 52초)

아이디어

각 비가 올 수 있는 높이 마다
BFS를 돌며 최대 영역의 개수를 탐색한다.(개수가 아니라 너비로 보고 이해가 안되어서 시간을 좀 낭비함)

그래서 최악의 경우의 수를 가정해보면
그럼 높이가 최대 100이고 map의 최대넓이는 100100이므로
100번의 BFS를 돈다고 가정하고 사실 각 배열마다 탐색할 일은 문제의 가정상 별로 없겠지만
최악을 가정한다고 했을때그험 100100*100이므로 충분히 가능한 시간으로 보인다.
그래서 매 비의 높이에 맞워서 안전영역이 가능한 지점을 발견하면 BFS를 돌아서
안전 영역에 대한 개수를 세고 해당 비의 높이에 해당하는 안전영역의 수를
최대와 비교하여 출력해준다.

풀이코드

import java.io.*;
import java.util.*;
public class Main {
    static int N, result;
    static int [][] map;
    static boolean [][] visited;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int [N][N];
        result = 0;
        int maxHeight = -1;
        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                int height = Integer.parseInt(st.nextToken());
                maxHeight = Math.max(maxHeight, height);
                map[i][j] = height;
            }
        }
        for(int rain=0; rain<=maxHeight; rain++){
            //각 비의 높이 마다 BFS돌기
            visited = new boolean[N][N];
            int count = 0;
            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    if(map[i][j]>rain && !visited[i][j]){
                        BFS(i, j, rain);
                        count++;
                    }
                }
            }

            result = Math.max(result, count);
        }
        System.out.print(result);
    }

    static int [] dx = {1, 0, -1, 0};
    static int [] dy = {0, 1, 0, -1};
    static void BFS(int i, int j, int rain){
        ArrayDeque<int []> q = new ArrayDeque<>();
        q.add(new int[]{i, j});
        visited[i][j] = true;
        while (!q.isEmpty()){
            int [] cur = q.poll();
            int x = cur[0];
            int y = cur[1];
            for(int dir = 0; dir<4; dir++){
                int mx = x+dx[dir];
                int my = y+dy[dir];
                if(canGo(mx, my)&&!visited[mx][my]&&map[mx][my]>rain){
                    q.add(new int []{mx, my});
                    visited[mx][my] = true;
                }
            }
        }
    }
    static boolean canGo(int x, int y){
        return x<N&&y<N&&x>=0&&y>=0;
    }
}