60 삐약 : 백준 2468| 안전 영역 [바킹독 문제 풀이|BFS|JAVA]

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

 

 

package BKD_0x9_BFS;

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

public class BOJ_2468 {
    static int[][] input;
    static int[][] visited;

    static int N;

    static int[] dx ={0,1,0,-1};
    static int[] dy ={1,0,-1,0};



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

        int max_height=0;
        int max_num=0;

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                int area_height =Integer.parseInt(st.nextToken());
                max_height = Math.max(area_height, max_height);
                input[i][j] = area_height;

            }
        }

        for(int i=0;i<=max_height;i++){
            int num_area=0;
            visited = new int[N][N];

           for(int j=0;j<N;j++){
               for(int k=0;k<N;k++){
                   if(visited[j][k]==0 &&input[j][k]>i){
                       bfs(j,k,i);
                       num_area++;
                   }
               }
           }
            max_num = Math.max(num_area,max_num);

        }
        System.out.println(max_num);
    }

    public static class Pair{
        int x;
        int y;

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

    public static void bfs(int x, int y, int h){
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(x,y));
        visited[x][y]=1;

        while (!q.isEmpty()){
            Pair p = q.poll();

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

                if(nx>=0 && ny>=0 && nx<N && ny<N && input[nx][ny]>h && visited[nx][ny]==0){
                    visited[nx][ny]=1;
                    q.offer(new Pair(nx,ny));
                }
            }

        }

    }
}

 

 

이전에 적용했던 bfs를 활용하면 충분히 풀 수 있는 문제였다.

근데 3트만에 성공했는데 그 이유가 말이댜

 

첫번째에는 입력받는 값 N이 빌딩의 높이 기준이라고 인지해버려서 2이상 max_height 이하로 탐색을 시작해서 틀렸고

 

두 번째에는 건물 높이가 1부터인걸 확인하고 1이상 최고 높이 이하로 탐색했다가 틀렸다 ㅇㅅㅇ...

 

탐색을 0부터 해야했었다.. 그럼 비가 안 온 건가....

 

모쪼록 장마로 인한 홍수 피해가 없으셨다니 다행이댜....