백준 2468번: 안전 지역

문제 설명

• https://www.acmicpc.net/problem/2468
• 비가 h만큼 온다면 h>=board[i][j]인 (i,j)지역은 물에 잠깁니다.
  • 침수된 지역을 제외한 나머지 지역에서 이동 가능한 곳을 연결한 섬의 개수를 구합니다.
  • 비가 1~100만큼 올 때 섬의 개수가 가장 많은 경우는 몇 개의 섬이 생기는지를 구합니다.

접근법

• 침수된 지역을 구하는 BFS, 침수 후 섬의 개수를 구하는 BFS를 각각 실행했습니다.

pseudocode

for(h는 1부터 가장 높은 지점의 숫자까지){
	// 높이가 h 이하인 지역이 물에 잠깁니다.
    for(i는 0부터 N까지){
        for(j는 0부터 N까지){
            BFS(i,j,h);
        }
    }
    // 섬의 개수를 구합니다.
    for(i는 0부터 N까지){
        for(j는 0부터 N까지){
	        // 1001은 임의의 숫자입니다. 저는 물에 잠긴 지역을 1002로 표현했습니다.
            // 섬을 구하기 위해서는 100(지역의 최대높이) < x <1002(물에 잠긴 걸 표현)를 만족하는 x로 BFS를 실행해야 합니다.
            BFS(i,j,1001); 
        }
    }
    
}

정답

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

class Main {
	static int MaxHeight = 0;
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, -1, 0, 1 };
	static int N;
	static int Answer = 1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		int[][] board = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int val = sc.nextInt();
				board[i][j] = val;
				MaxHeight = Math.max(val, MaxHeight);
			}
		}
		for (int h = 1; h <= MaxHeight; h++) {
			int[][] CopyBoard = new int[N][N];
			for (int i = 0; i < N; i++) {
				CopyBoard[i] = board[i].clone();
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					BFS(i, j, h, CopyBoard);
				}
			}

			int cnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (CopyBoard[i][j] < 1002) {
						cnt++;
						BFS(i, j, 1001, CopyBoard);
					}
				}
			}
			Answer = Math.max(Answer, cnt);
		}
		System.out.println(Answer);

	}

	public static void BFS(int x, int y, int h, int[][] board) {
		Queue<int[]> q = new LinkedList<int[]>();
		int[] temp = { x, y };
		q.add(temp);
		while (!q.isEmpty()) {
			int[] now = q.poll();
			for (int d = 0; d < 4; d++) {
				int nx = now[0] + dx[d];
				int ny = now[1] + dy[d];
				if (0 <= nx && nx < N && 0 <= ny && ny < N && board[nx][ny] <= h) {
					int[] next = { nx, ny };
					q.add(next);
					board[nx][ny] = 1002;
				}
			}
		}
	}
}