# BOJ02468 안전 영역
https://www.acmicpc.net/problem/2468 (opens new window)
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.
장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다.
어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산한다.
# Location
좌표 관리를 위한 Location 클래스이다.
private static class Location {
private int x;
private int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
# 잠긴 지역 확인
원본 배열을 기준으로 물에 잠긴 지역과 잠기지 않은 지역을 copy한다.
// 원본 배열을 기준으로 물에 잠긴 지역과 잠기지 않은 지역을 구분한다.
private static void change(int standard) {
copyGraph = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (standard >= graph[i][j]) {
copyGraph[i][j] = 0; // 물에 잠긴 지역
} else {
copyGraph[i][j] = 1; // 물에 잠기지 않은 안전한 지역
}
}
}
}
# bfs
복사한 그래프를 기준으로 너비 우선 탐색을 진행하며 잠긴 지역을 체크한다.
private static void bfs(int x, int y) {
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(x, y));
copyGraph[x][y] = -1;
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int i = 0; i < 4; i++) {
x = location.x + dx[i];
y = location.y + dy[i];
if (isLocation(x, y)) {
queue.add(new Location(x, y));
copyGraph[x][y] = -1;
}
}
}
}
private static boolean isLocation(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n || copyGraph[x][y] == 0 || copyGraph[x][y] == -1) {
return false;
}
return true;
}
# 제출 코드
아래는 최종 제출 코드이다.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class BOJ2468 {
private static int n;
private static int[][] graph;
private static int[][] copyGraph;
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, -1, 1};
private static class Location {
private int x;
private int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
private static void bfs(int x, int y) {
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(x, y));
copyGraph[x][y] = -1;
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int i = 0; i < 4; i++) {
x = location.x + dx[i];
y = location.y + dy[i];
if (isLocation(x, y)) {
queue.add(new Location(x, y));
copyGraph[x][y] = -1;
}
}
}
}
private static boolean isLocation(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n || copyGraph[x][y] == 0 || copyGraph[x][y] == -1) {
return false;
}
return true;
}
// 원본 배열을 기준으로 물에 잠긴 지역과 잠기지 않은 지역을 구분한다.
private static void change(int standard) {
copyGraph = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (standard >= graph[i][j]) {
copyGraph[i][j] = 0; // 물에 잠긴 지역
} else {
copyGraph[i][j] = 1; // 물에 잠기지 않은 안전한 지역
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
graph = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = scanner.nextInt();
}
}
// 안전 구역의 개수를 저장하기 위한 list
List<Integer> safeAreas = new ArrayList<>();
for (int l = 0; l <= 100; l++) {
change(l);
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 안전 지역이거나 이미 탐색하지 않은 지역인 경우
if (copyGraph[i][j] == 1) {
bfs(i, j);
count++;
}
}
}
safeAreas.add(count);
}
int max = 0;
for (Integer safeArea : safeAreas) {
max = Math.max(max, safeArea);
}
System.out.println(max);
}
}