[백준](Java) 2468 - 안전 영역

문제 링크

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

문제 풀이

비에 잠기는 범위를 제한 하기 위해
map에 값을 넣으면서 가장 낮은값과, 가장 높은값을 알아냈다.

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                map[i][j] = sc.nextInt();
                minnum = Math.min(minnum, map[i][j]);
                maxnum = Math.max(maxnum, map[i][j]);
            }
        }

전체 큰 for문은 가장 낮은값부터, 가장 높은 값까지 반복하는 for문이며 그 안에서
물에 잠기는 지역의 값은 0으로 만들어주었다.

            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(map[i][j]<=k){
                        map[i][j]=0;
                    }
                }
            }

그리고 chk를 전부 false로 만들어주어 다시 bfs를 탐색하도록 만들었다.

           for(int i=0; i<n; i++){
                Arrays.fill(chk[i], false);
            }

그리고 다시 맵을 돌며 아직 물에 잠기지 않았으며, 방문하지 않은곳으로 bfs 탐색을 시작한다.

           for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(!chk[i][j] && map[i][j]!=0){
                        bfs(i,j);
                    }
                }
            }

bfs를 진행할때마다 해당 강수량일때의 안전한 지역을 나타내는 temp의 count가 올라가며

가장 안전한 지역이 많은 개수와 비교하며 그값을 answer로 하고

다시 temp를 초기화한다.

answer = Math.max(answer,temp);
            temp = 0;

코드

package bfs;

import java.util.*;

public class BJ2468 {

    static int[][] map;
    static boolean[][] chk;
    static int temp =0;
    static int n;
    static int[] diry = {-1, 0, 1, 0}; //상 우 하 좌
    static int[] dirx = {0, 1, 0, -1};
    
    public static class Node {
        int y;
        int x;

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

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int answer =1;
        int minnum = Integer.MAX_VALUE;
        int maxnum = Integer.MIN_VALUE;
        n = sc.nextInt();
        map = new int[n][n];
        chk = new boolean[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                map[i][j] = sc.nextInt();
                minnum = Math.min(minnum, map[i][j]);
                maxnum = Math.max(maxnum, map[i][j]);
            }
        }
        for(int k=minnum; k<=maxnum; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(map[i][j]<=k){
                        map[i][j]=0;
                    }
                }
            }
            for(int i=0; i<n; i++){
                Arrays.fill(chk[i], false);
            }

            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(!chk[i][j] && map[i][j]!=0){
                        bfs(i,j);
                    }
                }
            }
            answer = Math.max(answer,temp);
            temp = 0;
        }

        System.out.println(answer);

    }

    public static void bfs(int y, int x){
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(y,x));
        chk[y][x]=true;
        while(!queue.isEmpty()){
            Node now = queue.poll();
            for(int i=0; i<4; i++){
                int now_y = now.y+diry[i];
                int now_x = now.x+dirx[i];
                if(now_y>=0 && now_y<n && now_x>=0 && now_x<n){
                    if(!chk[now_y][now_x] && map[now_y][now_x]!=0){
                        queue.add(new Node(now_y,now_x));
                        chk[now_y][now_x] = true;
                    }
                }
            }
        }
        temp++;

    }
}