[백준 2468] - [DFS BFS] - 안전영역 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/2468

---

이 문제는 정말 분노를 유발하는 문제였다. 

일단 문제를 풀기에 앞서 이문제를 풀기전에 꼭 명심해야할 사항을 먼저 적고 시작하겠다.

각 영역의 높이를 기준으로 문제를 풀면 틀린다. 비가 안왔을 경우에 대해서도 처리를 해야한다.

위의 말이 무엇인지는 문제를 풀다보면 이해가 저절로 갈것이라 생각한다.

계속 문제가 틀렸다 나오길래 멘탈이 무너진 상태에서 질문 검색을 통해 확인해보니 비가 온 높이로 잠기는 안전영역을 확인하는것이었다. 

안전 영역 자체의 높이로만 DFS 혹은 BFS 탐색을 돌리면 비가 안왔을 경우인  비의 높이 0 에대해서 대응을 하지 못하기 때문에 계속 틀리다는 결과를 받았다.

문제가 매우 모호한 문제이기에 이 문제를 헤매고 있는 다른 사람들도 꼭 위의 주의사항을 꼭 읽어 줬으면 한다. 

이 문제는 각 영역에 대한 높이를 입력 받을때 우선순위 큐에다가 높이 정보를 삽입 했다. 

만약 안전구역이 2 또는 4로만 구성 돼 있을경우 비가 높이 2가 오던지 3이 오던지  높이가 2인 안전구역은 다 잠기기 때문이다. 

그리고 높이 0도 우선순위 큐에 삽입했다. 

이게 이제 비가 안왔을 경우에 대한 처리 나타내는 것이다. 

좀 애매한게 높이가 0인 안전구역이 비가 안왔을 경우에도 잠긴것으로 처리 되는거 같다. 

좀 애매한 문제다.

이문제는 기분이 나쁜 문제이기 때문에 자세한 글을 남기싫다. 바로 소스 올려야겠다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    public static int size;
    public static int[][] arr;
    
    public static int min = Integer.MAX_VALUE;
    public static int max = Integer.MIN_VALUE;
    
    public static int cnt = 0;
    public static PriorityQueue<Integer> pq;
    
    public static int[] dy = {-1, 1, 0, 0}; // 상 하 좌 우
    public static int[] dx = {0, 0, -1, 1}; // 상 하 좌 우
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        size = Integer.parseInt(br.readLine());
        arr = new int[size][size];
        pq = new PriorityQueue<>();
        
        pq.offer(0); // 비가 안왔을 경우를 대비해야 한다.
        
        for(int i=0; i < size; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < size; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(!pq.contains(arr[i][j]))pq.offer(arr[i][j]);
                min = (min > arr[i][j])?arr[i][j]:min;
                max = (max < arr[i][j])?arr[i][j]:max;
            }
        }
        
        while(!pq.isEmpty()) {
            int h = pq.poll();
            
            boolean[][] visited = new boolean[size][size];
            int tCnt = 0;
            
            for(int i=0; i < size; i++) {
                for(int j = 0; j < size; j++) {
                    if(!visited[i][j] && arr[i][j] > h) {
                        dfs(h,i,j,visited);
                        tCnt += 1;
                    }
                }
            }
            
           cnt = Math.max(cnt, tCnt);
        }
        System.out.println(cnt);
    }
    
    public static void dfs(int h, int y, int x, boolean[][] visited) {
        visited[y][x] = true;
        
        for(int i=0; i < 4; i++) {
            int yy = dy[i] + y;
            int xx = dx[i] + x;
            
            if(yy < 0 || xx < 0 || yy >= size || xx >= size) continue;
            if(arr[yy][xx] <= h) continue;
            if(visited[yy][xx]) continue;
            dfs(h, yy, xx, visited);
        }
    }
}