백준 2468 - 안전 영역

큰모래·2023년 4월 11일

백준

문제

2468번: 안전 영역

조건

NxN 행렬이 주어진다.
각 칸은 값은 그 지역의 높이를 의미한다.
이어져 있으면 하나의 영역으로 친다.
물에 잠기지 않는 안전한 영역의 최대 개수 계산

접근법

비의 양 - 1

침수지역 X → 안전한 영역 : 1개

비의 양 - 2

안전한 영역 : 1개

비의 양 - 3

안전한 영역 : 4개

어떻게 풀어야 할까??

입력 받은 배열의 최대 높이를 계산한다. (예제에서는 9)
비의 양이 1인 경우부터 최대 높이 만큼 내리는 경우까지 각각 계산한다.
특정 영역의 모든 노드를 빠르게 탐색 → DFS 사용하는게 좋지만 저는 BFS로 풀어봤습니다.

문제 풀이 - BFS


public class p2468 {

	// 입력으로 받는 높이를 저장하는 배열
    public static int[][] arr;
		
	// 방문한 지역인지 확인하는 배열 
    public static boolean[][] visited;

	// 입력받는 행렬의 크기
    public static int N;

	// 현재 위치에서 상하좌우로 움직이기 위한 배열
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

	// bfs에서 사용할 큐(2차원 배열의 위치 정보를 저장해야 하므로 Point 클래스를 제네릭으로 선언)
    public static Queue<Point> queue = new LinkedList<>();

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

        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];

		// 행렬의 최대 높이를 구하기 위한 변수
        int maxNumber = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                maxNumber = Math.max(maxNumber, arr[i][j]);
            }
        }

				
		// 최대 높이가 1 -> 모든 값 1로 채워져있는 배열 -> 비가 안오는 경우가 최선
        if (maxNumber == 1) {
            System.out.println(1);
        } 
        
        else {
			// 모든 경우의 수 중 땅덩어리를 가장 많이 가지는 경우를 저장하기 위한 변수
            int maxCount = 0;

			// t = 비의 양, maxNumber만큼 비오면 모든 땅 다 침수
            for (int t = 1; t < maxNumber; t++) {
				// 비의 양이 달라질때마다 visitied 배열 초기화
                visited = new boolean[N][N];
                
				// bfs를 돌려 얻은 현재 상황의 땅 덩어리 개수와 기존 maxCount 비교
                maxCount = Math.max(find(t), maxCount);
            }

            System.out.println(maxCount);
        }
    }

	// 매개변수로 비의 양을 넣어준다.
    public static int find(int rainCount) {

		// 땅덩어리 개수를 저장하는 변수
        int count = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
				// 땅의 높이가 비의 양보다 높고 방문하지 않은 지역일 경우
                if (arr[i][j] > rainCount && !visited[i][j]) {
					// 무조건 새로운 땅덩어리(지역)이므로 count++
                    count++;
                    visited[i][j] = true;
                    queue.add(new Point(i, j));

					// 현재 들어온 땅에 발자국을 다 남길때까지 반복
                    while (!queue.isEmpty()) {
                        Point p = queue.poll();

						// 현재 위치에서 상하좌우로 이동
                        for (int t = 0; t < 4; t++) {

                            int nx = p.x + dx[t];
                            int ny = p.y + dy[t];
							// 일단, nx,ny가 0 이상이며 N보다 작아야 행렬 안에 있다.
                            if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
		
								// 행렬 안에 위치해있다면, 현재 위치가 비의 양보다 커야한다.
								// 그리고 방문하지 않은 땅이어야 한다.
                                if (arr[nx][ny] > rainCount && !visited[nx][ny]) {
									// 조건 충족하면 큐에 넣고 방문처리
                                    queue.add(new Point(nx, ny));
                                    visited[nx][ny] = true;
                                }
                            }
                        }
                    }
                }

            }
        }
        return count;
    }
}