[백준] 2468번 안전 영역

 안전 영역 문제는 장마철 비가 어느정도 왔을때 안전영역의 갯수가 최대가 되는지 구하는 문제 입니다. 강수량을 확인해서 침수 영역을 만들어주었습니다. 그 후에는 안전구역을 BFS 알고리즘을 사용해서 확인 했습니다. 더 이상 탐색할 곳이 없다면 안전 구역의 번호를 1 증가 시키고 다음 영역을 탐색하였습니다. 처음에는 안전구역이 가장 넓은 경우를 찾는 문제라고 생각했고 비가 가장 조금 왔을 경우에 안전구역이 넓어질 것이라고 생각했습니다. 그러나 안전 구역의 넓이가 아니라 안전 구역이 만들어진 갯수의 최댓값을 구하는 문제인 것을 확인하고 강수량이 될 수 있는 1부터 100까지 모든 경우에서 확인을 하였습니다. 프로그램의 실행 시간을 조금이라도 줄일려면 입력된 구역에서 가장 높은 위치의 값과 강수량을 비교해서 가장 위치가 높은 경우보다 강수량이 많아지면 프로그램을 중지하는 방법을 사용하면 더 효율적인 코드가 될 것이라고 생각합니다. 아래는 문제와 소스 코드 입니다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class SafeArea {

	int n;
	int[][] map;
	boolean[][] check;
	int[][] safeArea;
	int[] dRow = { 0, 0, 1, -1 }, dCol = { 1, -1, 0, 0 };
	int max;

	void bfs(int sRow, int sCol, int num) {
		Queue<Pair<Integer, Integer>> q = new LinkedList<Pair<Integer, Integer>>();
		Pair<Integer, Integer> tempPair = new Pair<Integer, Integer>(sRow, sCol);
		int nRow, nCol;
		int tempRow, tempCol;

        safeArea[sRow][sCol] = num;
        check[sRow][sCol] = true;
		q.add(tempPair);
		while (!q.isEmpty()) {
			tempPair = q.poll();
			tempRow = tempPair.x;
			tempCol = tempPair.y;
			for (int i = 0; i < 4; i++) {
				nRow = tempRow + dRow[i];
				nCol = tempCol + dCol[i];
				if (0 <= nRow && nRow < n && 0 <= nCol && nCol < n) {
					if(check[nRow][nCol] == false && safeArea[nRow][nCol] == 0){
						check[nRow][nCol] = true;
						safeArea[nRow][nCol] = num;
						tempPair = new Pair<Integer, Integer>(nRow, nCol);
						q.add(tempPair);
					}
				}
			}
		}
	}

	void checkSafeArea(int limit) {
		int num = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] <= limit) {
					check[i][j] = true;
				}
			}
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (check[i][j] == false && safeArea[i][j] == 0) {
					bfs(i, j, ++num);
				}
			}
		}
		
		if (num > max) {
			max = num;
		}

		recovery();
	}

	void recovery() {
		for(int i=0;i<n;i++){
			Arrays.fill(check[i], false);
			Arrays.fill(safeArea[i], 0);
		}
	}

	void solution() {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		map = new int[n][n];
		check = new boolean[n][n];
		safeArea = new int[n][n];

		max = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = sc.nextInt();
			}
		}
        
		for (int i = 0; i <= 100; i++) {
			checkSafeArea(i);
		}

		System.out.println(max);
	}

	public static void main(String[] args) {
		SafeArea m = new  SafeArea();
		m.solution();
	}

	class Pair<X, Y> {
		X x;
		Y y;

		public Pair(X x, Y y) {
			this.x = x;
			this.y = y;

		}

	}

}