문제

백준 2468번
https://www.acmicpc.net/problem/2468

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

---

생각하기

일반 DFS/BFS에서 안전영역으로 설정해줄 범위만 정해주면 비교적 쉬운 문제였다.

동작

	static List<Integer> list = new ArrayList<>();
	static int dirX[] = {0, 0, -1, 1}; // 상 하 좌 우
	static int dirY[] = {-1, 1, 0, 0}; // 상 하 좌 우
	static boolean visit[][];
	static int arr[][];

	static int N, nowX, nowY;

지도를 생성할 배열과 방문여부를 저장할 배열을 만들어주고,
list는 각 안전영역의 높이를 저장할 list이다.
총 높이의 종류인 길이가 얼마가 될지 모르기때문에 List로 설정했다.

		int max = Integer.MIN_VALUE / 16;
		for(int num : list) {
			visit = new boolean[N][N];
			int safeArea = 0;

			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {

					if( !visit[i][j] && arr[i][j] >= num) {
						DFS(i, j, num);
						safeArea++;
					}
				}
			}

			max = Math.max(max, safeArea);
		}

list에 들어있는 높이의 값 개수 만큼 반복하도록 먼저 설정해주고
전체 arr을 반복한다.

안전영역을 판단하기 위해서 잠기는 높이를 계속 바꾸면서 최대값을 갱신해야 하기 때문이다.

이후 DFS메소드 내부는 특이점이 없다.

---

코드

DFS

import java.util.*;
import java.io.*;

public class Main {
	static List<Integer> list = new ArrayList<>();
	static int dirX[] = {0, 0, -1, 1}; // 상 하 좌 우
	static int dirY[] = {-1, 1, 0, 0}; // 상 하 좌 우
	static boolean visit[][];
	static int arr[][];

	static int N, nowX, nowY;

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

		N = Integer.parseInt(br.readLine());

		arr = new int[N][N];
		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());

				if( !list.contains(arr[i][j])) {
					list.add(arr[i][j]);
				}
			}
		}

		int max = Integer.MIN_VALUE / 16;
		for(int num : list) {
			visit = new boolean[N][N];
			int safeArea = 0;

			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {

					if( !visit[i][j] && arr[i][j] >= num) {
						DFS(i, j, num);
						safeArea++;
					}
				}
			}

			max = Math.max(max, safeArea);
		}

		System.out.println(max);
	} // End of main

	static void DFS(int x, int y, int num) {
		visit[x][y] = true;

		for(int i=0; i<4; i++) {
			nowX = x + dirX[i];
			nowY = y + dirY[i];

			if(range_check() && visit[nowX][nowY] == false && arr[nowX][nowY] >= num) {
				DFS(nowX, nowY, num);
			}
		}

	} // End of DFS

	static boolean range_check() {
		return (nowX >= 0 && nowY >= 0 && nowX < N && nowY < N); >
	} // End range_check

} // End of Main class