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

문제

0부터 100까지 비가 온다고 했을 때 안전영역이 가장 많았을 때 안전영역의 수를 출력

풀이

map에 0부터 100까지 비가 왔을 때 이중 for문을 돌려서 bfs를 할 수 있는 곳을 찾는다. bfs를 할 수 있으면 안전영역의 시작점이므로 안전영역의 개수를 구할 수 있다. 비가 새로 내릴 때 마다 visit 배열을 초기화해야 한다.

코드

for (int i = 0; i <= max; i++) {
            water = i;
            visit = new boolean[N][N];
            int temp = 0;

0부터 map의 최대값까지 비를 내린다.
visit배열은 초기화 시켜준다.
안전영역의 수를 임시로 넣어줄 temp를 준비한다.

for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    if(map[j][k]<=water)continue;
                    if(visit[j][k])continue;
                    temp++;
                    bfs(j, k);
                }
            }

만약 물에 잠겼거나 방문한 적이 있다면 continue
아니라면 안전영역 수를 1늘리고 bfs를 진행한다.

private static void bfs(int r, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r, c});
        visit[r][c] = true;
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int curR = poll[0];
            int curC = poll[1];
            for (int i = 0; i < 4; i++) {
                int newR = curR + dir[i][0];
                int newC = curC + dir[i][1];
                if(newR < 0 || newC < 0 || newR >= N || newC >= N) continue;
                if(visit[newR][newC])continue;
                if(map[newR][newC] <= water)continue;
                visit[newR][newC] = true;
                queue.add(new int[]{newR, newC});
            }

        }
    }

bfs코드이다.

전체코드

package baekjoon._2468;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        input();
        pro();
    }

    static int N, max, water;
    static int[][] map;
    static boolean[][] visit;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void input() {
        FastReader fr = new FastReader();
        N = fr.nextInt();
        map = new int[N][N];
        max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int cur = fr.nextInt();
                map[i][j] = cur;
                max = Math.max(max, cur);
            }
        }
    }

    public static void pro() {
        int ans = 0;
        for (int i = 0; i <= max; i++) {
            water = i;
            visit = new boolean[N][N];
            int temp = 0;
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    if(map[j][k]<=water)continue;
                    if(visit[j][k])continue;
                    temp++;
                    bfs(j, k);
                }
            }
            ans = Math.max(ans, temp);
        }
        System.out.println(ans);
    }

    private static void bfs(int r, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r, c});
        visit[r][c] = true;
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int curR = poll[0];
            int curC = poll[1];
            for (int i = 0; i < 4; i++) {
                int newR = curR + dir[i][0];
                int newC = curC + dir[i][1];
                if(newR < 0 || newC < 0 || newR >= N || newC >= N) continue;
                if(visit[newR][newC])continue;
                if(map[newR][newC] <= water)continue;
                visit[newR][newC] = true;
                queue.add(new int[]{newR, newC});
            }

        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in));}

        String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        Double nextDouble() { return Double.parseDouble(next()); }

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            } catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}

느낀점

처음 문제를 봤을 때 저번에 풀었던 파괴되지않은건물 문제가 생각이 났다. 하지만 이 문제는 누적합을 이용하는 것이 아니라 BFS를 활용한 문제이다. BFS 코드를 외워놨기 때문에 쉽게 풀 수 있는 문제였다.