BOJ 2468 안전 영역 (Java)

재귀와 반복문, 델타를 이용한 DFS & 방문체크

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int n, cnt;
	static int[][] height;			// 영역의 높이
	static boolean[][] visited;		// 방문체크
	static int[] dr = {0, 1, 0, -1};// 우 하 좌 상
	static int[] dc = {1, 0, -1, 0};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		height = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				height[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int max = 1;	// 비의 양이 0일 때, 안전영역 1
		for (int rain = 1; rain < 101; rain++) {
			visited = new boolean[n][n];
			cnt = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
                	// 안전영역이고, 체크한 적 없는 영역일 때
					if(height[i][j] > r && !visited[i][j]) {
                        visited[i][j] = true;
						cnt += 1;
						dfs(rain, i, j);
					}
				}
			}
			max = Math.max(max, cnt);
		} // end for r
		System.out.println(max);
	}
	static void dfs(int rain, int r1, int c1) {
		for (int d = 0; d < 4; d++) {
			int r2 = r1 + dr[d];
			int c2 = c1 + dc[d];
			
            // 인덱스 범위를 벗어났을 때
			if(r2 < 0 || r2 >= n || c2 < 0 || c2 >= n) continue;
            // 이미 체크했을 때
			if(visited[r2][c2]) continue;
			// 안전영역일 때
			if(height[r2][c2] > rain) {
				visited[r2][c2] = true;
				dfs(rain, r2, c2);
			}
		}
	}
}