boj)2468 - 안전 영역
2020. 10. 21. 18:09ㆍPS/boj
import java.io.*;
import java.util.*;
public class boj_2468 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, nx, ny, max;
static int[][] map = new int[100][100];
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static List<Integer> list = new ArrayList<>();
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] >= max) max = map[i][j];
}
}
// 0 <= h <= max
for (int i = 0; i <= max; i++) {
Queue<int[]> q = new LinkedList<>();
boolean[][] v = new boolean[N][N];
int ans = 0;
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (map[j][k] <= i) {
v[j][k] = true;
}
}
}
// bfs
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (!v[j][k]) {
v[j][k] = true;
q.offer(new int[] {j, k});
ans++;
}
while (!q.isEmpty()) {
int[] now = q.poll();
for (int l = 0; l < 4; l++) {
nx = now[0] + dx[l];
ny = now[1] + dy[l];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (!v[nx][ny]) {
v[nx][ny] = true;
q.offer(new int[] {nx, ny});
}
}
}
}
}
list.add(ans);
}
Collections.sort(list);
System.out.println(list.get(list.size()-1));
}
}
- 그 지역의 높이 이상의 비는 탐색 할 필요가 없으니 max값 추출
- 0~max까지의 비가 오는 경우 전부 체크
- 비가 왔을때 잠기는 부분 체크하고 bfs 탐색 후 list에 count 추가
- list에서 최댓값 출력
'PS > boj' 카테고리의 다른 글
boj)2573 - 빙산 (0) | 2020.10.24 |
---|---|
boj)1629 - 곱셈 (0) | 2020.10.23 |
boj)10026 - 적록색약 (0) | 2020.10.21 |
boj)7569 - 토마토 (0) | 2020.10.19 |
boj)1697 - 숨바꼭질 (0) | 2020.10.17 |