[BaekJoon] 2468 안전 영역

1.  문제 링크

https://www.acmicpc.net/problem/2468

2.  문제

요약

• 어떤 지역의 높이 정보가 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어집니다.
• 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 물에 잠기지 않는 안전한 영역이라고 하는데, 내리는 비의 양에 따라 물에 잠기지 않는 안전한 영역의 개수가 달라집니다.
• 지역의 높이 정보가 주어졌을 때, 물에 잠기지 않는 안전한 영역의 최대 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 100보다 작거나 같은 정수인 2차원 배열의 행과 열의 개수를 나타내는 수 N이 주어지고 두 번째 줄부터 N개의 줄에는 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 주어집니다. 높이는 1보다 크거나 같고 100보다 작거나 같은 정수입니다.
• 출력: 첫 번째 줄에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static int num;
	static int[][] heights;
	boolean[][] visited;
	
	public void dfs(int x, int y, int h) {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		visited[x][y] = true;
		for(int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];
			if(cx >= 0 && cx < num && cy >= 0 && cy < num) {
				if(!visited[cx][cy] && heights[cx][cy] > h) {
					dfs(cx, cy, h);
				}
			}
		}
	}
	
	public int getMaxNumOfSafety(int max) {
		int result = 0;
		for(int i = 0; i <= max; i++) {
			visited = new boolean[num][num];
			int count = 0;
			for(int j = 0; j < heights.length; j++) {
				for(int l = 0; l < heights[j].length; l++) {
					if(!visited[j][l] && heights[j][l] > i) {
						count++;
						dfs(j, l, i);
					}
				}
			}
			result = Math.max(result, count);
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		num = Integer.parseInt(br.readLine());
		heights = new int[num][num];
		int max = 0;
		for(int i = 0; i < num; i++) {
			String[] input = br.readLine().split(" ");
			for(int j = 0; j < num; j++) {
				heights[i][j] = Integer.parseInt(input[j]);
				max = Math.max(max, heights[i][j]);
			}
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxNumOfSafety(max) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DFS를 이용하여 해결할 수 있습니다.
• 비의 양이 0일 때부터 주어진 높이들에서 가장 높은 높이에 해당하는 양까지 물에 잠기지 않는 안전한 영역의 개수를 구합니다.
• 물에 잠기지 않는 안전한 영역의 개수를 구할 때는 해당 지역의 각 위치를 방문하였는지 여부를 알기 위한 boolean 타입의 2차원 배열을 생성하고 각 위치들을 방문하며 해당 위치가 아직 방문되지 않았고 비의 양보다 높이가 높은 경우에 해당 위치의 상하좌우를 살피며 물에 잠기지 않는 안전한 영역을 구합니다.
• 물에 잠기지 않는 안전한 영역을 모든 위치를 돌면서 찾고 찾을 때마다 개수를 1씩 올리면서 어떠한 비의 양일 때에 물에 잠기지 않는 안전한 영역의 개수를 구하고 모든 비의 양에서 개수를 구한 후에 가장 많은 개수를 출력합니다.

1. 높이들을 2차원 배열에 입력받으며 가장 높은 높이를 구합니다.
2. 0부터 가장 높은 높이까지 반복문을 돌면서 해당 값만큼 비가 왔을 때에 물에 잠기지 않는 안전한 영역의 개수를 구하고 그 중 가장 많은 개수를 구합니다.
   1. 각 위치를 방문하였는지를 나타내는 boolean 타입의 2차원 배열 visited를 생성하고 각 위치를 방문하면서 물에 잠기지 않는 안전한 영역의 개수를 구합니다.
   2. 각 위치를 방문할 때, 아직 해당 위치가 방문되지 않았고 해당 위치의 높이가 비의 양보다 높다면 물에 잠기지 않는 안전한 영역의 개수를 1 증가시키고 물에 잠기지 않는 안전한 영역을 구합니다.
      1. 상하좌우를 나타낼 dx, dy 배열을 생성하고 값을 설정하며 해당 위치를 방문했다는 의미로 해당 위치의 visited 값을 true로 변경합니다.
      2. 해당 위치의 상하좌우를 방문하여 해당 위치가 N * N 2차원 배열 내에 있고 아직 방문되지 않았으며 높이가 비의 양보다 높다면 해당 위치에서 다시 상하좌우를 확인하여 물에 잠기지 않는 안전한 영역을 구합니다.
   3. 모든 위치를 방문하여 해당 비의 양에서 물에 잠기지 않는 안전한 영역의 개수를 구한 후에 해당 개수와 이전의 개수 중 가장 큰 개수를 나타내는 result와 비교하여 물에 잠기지 않는 안전한 영역의 최대 개수를 result에 설정합니다.
3. 2번의 반복문이 끝났을 때에 result 값이 물에 잠기지 않는 안전한 영역의 최대 개수이므로 해당 값을 출력합니다.