[BOJ-2468][BFS] 안전 영역 - Java

문제 바로가기

2468번: 안전 영역

 

전형적인 BFS 문제입니다. 물에 잠기는 높이마다 체크해주면 됩니다.

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

class Dir{
    int y, x;
    Dir(int y, int x){
        this.y = y; this.x = x;
    }
}

public class Main {
    static int N;
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};
    static int[][] map;

    static boolean isIn(Dir c) {
        if(0<= c.y && c.y < N && 0<= c.x && c.x < N) return true;
        else return false;
    }

    static void bfs(Dir cur, boolean[][] map) {
        Queue<Dir> q = new LinkedList<Dir>();
        q.offer(cur);
        map[cur.y][cur.x] = true;

        while(!q.isEmpty()) {
            Dir c = q.poll();

            for(int i = 0; i< 4; i++) {
                Dir next = new Dir(c.y + dy[i], c.x + dx[i]);
                if(!isIn(next) || map[next.y][next.x] ) continue;
                q.offer(next);
                map[next.y][next.x] = true;
            }
        }
    }

    static int rainning(int height) {
        int cnt = 0;
        boolean[][] afterRain = new boolean[N][N];

        for(int i =0 ;i < N; i++) {
            for(int j = 0 ; j< N; j++) {
                if(map[i][j] <= height) afterRain[i][j] = true;
            }
        }

        for(int i =0 ;i < N; i++) {
            for(int j = 0 ; j< N; j++) {
                if(!afterRain[i][j]) {
                    cnt++;
                    bfs(new Dir(i, j), afterRain);
                }
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N =    Integer.parseInt(br.readLine());
        map = new int[N][N];
        int maxLen = 0;
        StringTokenizer st;
        int ans = 0;

        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());
                maxLen = Math.max(maxLen, map[i][j]);
            }
        }

        for(int i = 0; i< maxLen; i++) 
            ans = Math.max(ans, rainning(i));

        System.out.println(ans);
    }
}

우선 물에 잠기는 높이를 0부터 입력 데이터중 가장 큰 높이까지 반복문을 돌려서 체크해줍니다.

ranning 메소드에서 물에 잠기는 높이 height 를 파라미터로 받아와서 물에 잠기는 부분 = true, 잠기지 않는 부분 = false 로 하는 boolean 타입의 새로운 2차원 배열을 만들어줍니다.

 

이 배열에서 원소가 false인 부분만 들어가서 cnt를 올리고 BFS를 돌려줍니다. 이 때 cnt는 height만큼 물에 잠겼을 때 안전한 영역의 개수입니다.

 

cnt의 값을 받아오면서 main 메소드의 ans에 최댓값을 업데이트해주면 됩니다.

 

 

 

감사합니당 ^_^