[Java] 백준 BOJ / 2468번: 안전 영역

안전 영역

문제

문제 설명

건물들의 높이가 주어진 좌표 내에서 수면의 높이에 따른 안전지대 구역 개수의 최대값을 구하는 문제이다.

그래서 그냥 그래프를 DFS 로 돌면서 다 해보는 방법으로 해보기로 했다.

일단 건물들의 높이를 입력받으면서 최대 건물의 높이를 파악을 한 후 해당 높이까지만큼만 DFS를 돌리기로 했다.

for (int i = 0; i < n; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	for (int j = 0; j < n; j++) {
		arr[i][j] = Integer.parseInt(st.nextToken());
		if (arr[i][j] > maxHeight) {
			maxHeight = arr[i][j];
		}
	}
}

int max = 0;

for (int height = 1; height < maxHeight; height++) {
	// 그래프 탐색 구현
}

이렇게 완성된 틀 내에서 height는 1부터 maxHeight 까지 돌면서 visited 배열을 초기화 해줘야한다.

그 후에 구현될 이중 for문 내에서 DFS를 돌고 구역의 개수를 세주고 최대값을 구해주면 끝난다.

DFS는 영역이 끝날 때마다 1을 리턴하는 함수로 만들었고 기준 height 값이 끝날때마다 결과인 max 값을 초기화 해주는 것으로 구현했다.

for (int height = 0; height < maxHeight; height++) {
	visited = new boolean[n][n];
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j] && arr[i][j] > height) {
				cnt += dfs(i, j, height);
			}
		}
	}
	max = Math.max(max, cnt);
}
System.out.println(max);

위와 같이 구현했고 전체 코드는 아래와 같다.

---

코드

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

public class Main_2468 {
    static int n;
    static int[][] arr;
    static boolean[][] visited;
    static int maxHeight = 0;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 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];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] > maxHeight) {
                    maxHeight = arr[i][j];
                }
            }
        }

        int max = 0;

        for (int height = 0; height < maxHeight; height++) {
            visited = new boolean[n][n];
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (!visited[i][j] && arr[i][j] > height) {
                        cnt += dfs(i, j, height);
                    }
                }
            }
            max = Math.max(max, cnt);
        }
        System.out.println(max);
    }

    public static int dfs(int x, int y, int height) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1) {
                continue;
            }
            if (visited[nx][ny]) {
                continue;
            }
            if (arr[nx][ny] > height) {
                dfs(nx, ny, height);
            }
        }
        return 1;
    }
}