백준 2468 안전영역

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

소스코드

import java.io.*;
import java.util.*;
public class Main {
	static int N;
	static int Ans = 1;
	static int maxHeight = 0;
	static int[][] map;
	static boolean[][] v;	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];	
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				maxHeight = Math.max(maxHeight, map[i][j]);
			}
		}	
		for (int height = 1; height < maxHeight; height++) {
			v = new boolean[N][N];
			int area = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(map[i][j] > height && !v[i][j]) {
						dfs(i, j, height);
						area++;
					}
				}
			}
			Ans = Integer.max(Ans, area);
		}
		System.out.println(Ans);
	}
	private static void dfs(int r, int c, int height) {
		v[r][c] = true;
		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if(nr<0 || nc<0 || nr>= N || nc>= N || v[nr][nc]) continue;
			if (map[nr][nc] > height) dfs(nr, nc, height);
		}
	}
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
}

해결방법

• 비가 오지 않으면 안전구역의 최대 개수는 1이기 때문에 최소값은 1로 잡고 시작한다.
• 최고 높이만큼 비가 오면 안전구역이 0이 되기 때문에 최고 높이는 고려할 필요가 없다.
  따라서 1 ~ (최고높이 -1) 까지 반복했을 때 안전구역의 최대 개수를 구하면 된다.
• 2차원 배열에서 안전구역을 발견하면 DFS를 수행하고 수행 횟수가 안전구역의 개수가 된다.
• 높이를 변화하면서 안전구역의 최대 개수를 저장