알고리즘(BOJ)/Silver
백준 - 안전 영역 2468
ch.0
2023. 2. 9. 17:14

문제 분석
비가 오는 높이를 1씩 높혀주면서 잠긴곳은 0 으로 바꿔주었다.
그리고 BFS를 태워서 0이아닌곳이 막힐때까지 0으로 확장시켜 주었다.
전체 소스
import java.util.*;
import java.io.*;
public class Main {
static int size, cnt, result;
static int[][] array;
public static void bfs() {
Queue<int[]> q = new LinkedList<>();
boolean[][] visited = new boolean[size][size];
boolean check = true;
int[][] array_c = new int[size][size];
for(int i=0; i<array.length; i++) {
array_c[i]=array[i].clone();
}
cnt=0;
while (check) {
check = false;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (array_c[i][j] != 0) {
array_c[i][j] = 0;
visited[i][j] = true;
q.offer(new int[] { i, j });
check = true;
cnt++;
break;
}
}
if (check == true)
break;
}
int[] x_move = { 0, 0, -1, 1 };
int[] y_move = { -1, 1, 0, 0 };
while (!q.isEmpty()) {
int[] p = q.poll();
int x = p[0];
int y = p[1];
for (int i = 0; i < 4; i++) {
int x_p = x + x_move[i];
int y_p = y + y_move[i];
if (x_p >= 0 && y_p >= 0 && x_p < size && y_p < size) {
if (array_c[x_p][y_p] != 0 && visited[x_p][y_p] == false) {
array_c[x_p][y_p] = 0;
visited[x_p][y_p] = true;
q.offer(new int[] { x_p, y_p });
}
}
}
}
}
if (result < cnt) {
result = cnt;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
size = Integer.parseInt(st.nextToken());
array = new int[size][size];
int max = -9999;
for (int i = 0; i < size; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < size; j++) {
array[i][j] = Integer.parseInt(st.nextToken());
if (max < array[i][j])
max = array[i][j];
}
}
for (int b = 0; b <= max; b++) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (b >= array[i][j])
array[i][j] = 0;
}
}
bfs();
}
System.out.println(result);
}
}

https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net