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

백준 2468번 문제 - 안전 영역

2468번: 안전 영역

---

문제 분석

 

 

 

• 지역 N * N 개의 높이를 배열 형태로 입력 받았을 때, 가장 많은 안전 영역 덩어리 개수를 출력해라.
  • 지역의 높이가 물이 잠긴 높이보다 클 경우 안전 영역
  • 안전 영역 덩어리 : 안전영역으로만 이루어진 덩어리 (이해를 쉽게 하기 위해 필자가 만든 용어)

---

 

해결 키 포인트

 

• 지역이 잠긴 경우의 수를 다 했을 때 ! 가장 많은 덩어리 수를 알아내야하므로 모든 방법을 탐색해야함
  → BFS 사용
• 가장 높은 지역 높이(max) 알아내기 : 빙산 높이까지 잠기는 경우의 수를 다 탐색해야 하므로 !
• 지역이 물에 잠기는 높이가 0부터 max까지 반복하면서 덩어리 개수 알아내기
  • 처음 위치를 큐에 넣고, 반복하면서 하나의 덩어리 알아내기 (방문 기록 해야지 다시 확인 안함)
  • 덩어리 확인할 때마다 result++;
• 모두 확인시 가장 큰 덩어리 개수 알아내 출력

---

 

코드

 

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

public class Main {
    public static int N;
    public static int [][] lists;
    public static boolean [][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        int max = 0;

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

        int result = 0;

        for (int m = 0; m <= max; m++) {
            int newResult = 0;
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(!visited[i][j] && lists[i][j] > m) {
                        BFS(i, j, m);
                        newResult++;
                    }
                }
            }
            result = Math.max(result, newResult);
        }

        System.out.println(result);
    }
    public static void BFS(int x, int y, int rainHeight) {
        Queue<Node> queue = new LinkedList<>();

        queue.add(new Node(x,y));
        visited[x][y] = true;

        while(!queue.isEmpty()) {
            Node value = queue.poll();

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

            for (int i = 0; i < 4; i++) {
                int newX = value.x + dx[i];
                int newY = value.y + dy[i];
                if(newX >= 0 && newY >= 0 && newX < N && newY < N
                        && lists[newX][newY] > rainHeight && !visited[newX][newY]) {
                    visited[newX][newY] = true;
                    queue.add(new Node(newX, newY));
                }
            }
        }
    }

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