BOJ_S1_2468

📁 [S1_2468] 안전 영역

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

public class Main{
	static StringTokenizer st;
	static int N, res;
	static int[][] arr;
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 행열의 개수
		N = Integer.parseInt(br.readLine());

		arr = new int[N][N];

		// 가장 높은 높이
		int max = 0;
		
		// 안전한 영역의 최대 개수
		int res_max = 0;

		// 높이 입력
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				max = Math.max(arr[i][j], max);
			}
		}
		for (int i = 0; i < max; i++) {
			res = 0;

			// 깊이가 낮은 것은 true 처리
			boolean[][] v = new boolean[N][N];
			for (int j = 0; j < N; j++) {
				for (int z = 0; z < N; z++) {
					if (arr[j][z] <= i) {
						v[j][z] = true;
					}
				}
			}

			for (int j = 0; j < N; j++) {
				for (int z = 0; z < N; z++) {
					// 방문하지 않았거나 잠기지 않았으면 dfs 실행
					if (!v[j][z]) {
						dfs(j, z, v);
						res++;
					}
					else {
						continue;
					}
				}
			}
			res_max = Math.max(res, res_max);
		}
		System.out.println(res_max);
	}
	
	// boolean 배열에 true 입력해주는 역할 
	static void dfs(int y, int x, boolean[][] v) {
		
		// 기저조건 : 잠기지 않은 지역 다 
		if (v[y][x]) {
			return;
		}
		
		// 잠기지도 않고 방문하지도 않았으면
		if(!v[y][x]) {
			v[y][x] = true;
		
		int nx, ny;
		for (int i = 0; i < 4; i++) {
			nx = x + dx[i];
			ny = y + dy[i];

			// 범위를 벗어
			if (nx < 0 || ny < 0 || nx >= N || ny >= N) {
				continue;
			}
			
			dfs(ny, nx, v);
			}
		}
	}
}

🤔 나의 생각

먼저 문제를 이해해보자면 높이가 다양한 지역들이 있다. 비가 오는 양에 따라 지역이 잠기냐 마냐가 결정 된다.
비가 많이 와서 물에 잠기지 않은 지역들은 상하좌우로 연결되어 있으면 한 공간으로 판단한다. 대각선은 연결이라고 치지 않는다.
그 공간들의 총 개수를 구하는 것이다. 그 총 개수들 중 안전한 영역의 최대 개수를 구하는 것이 문제이다.
한 마디로 비가 내려서 양이 1, 2, 3, 4 .. 일 때마다 잠기는 경우가 다 다르고 거기에 따라 안전한 영역의 개수가 다 다른데 그 때 안전한 영역의 최대 개수를 구하는 것이다.
나는 비가 와서 잠긴 부분과 이미 검사를 한 부분을 boolean 배열에서 true 부분이라 설정하고 완전탐색을 하며 false 부분에서 dfs 탐색을 해주었다.
dfs 탐색 한 번 할 때마다 카운팅을 해주어 비의 양마다 카운팅들을 비교해 최대값을 구했다.
dfs, bfs 어느 것을 쓰나 상관없지만 나는 dfs 가 더 편해서 dfs를 사용하였다.