https://www.acmicpc.net/problem/2468
0부터 100까지 비가 온다고 했을 때 안전영역이 가장 많았을 때 안전영역의 수를 출력
map
에 0부터 100까지 비가 왔을 때 이중 for
문을 돌려서 bfs
를 할 수 있는 곳을 찾는다. bfs
를 할 수 있으면 안전영역의 시작점이므로 안전영역의 개수를 구할 수 있다. 비가 새로 내릴 때 마다 visit
배열을 초기화해야 한다.
for (int i = 0; i <= max; i++) {
water = i;
visit = new boolean[N][N];
int temp = 0;
0부터 map
의 최대값까지 비를 내린다.
visit
배열은 초기화 시켜준다.
안전영역의 수를 임시로 넣어줄 temp
를 준비한다.
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if(map[j][k]<=water)continue;
if(visit[j][k])continue;
temp++;
bfs(j, k);
}
}
만약 물에 잠겼거나 방문한 적이 있다면 continue
아니라면 안전영역 수를 1늘리고 bfs
를 진행한다.
private static void bfs(int r, int c) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{r, c});
visit[r][c] = true;
while (!queue.isEmpty()) {
int[] poll = queue.poll();
int curR = poll[0];
int curC = poll[1];
for (int i = 0; i < 4; i++) {
int newR = curR + dir[i][0];
int newC = curC + dir[i][1];
if(newR < 0 || newC < 0 || newR >= N || newC >= N) continue;
if(visit[newR][newC])continue;
if(map[newR][newC] <= water)continue;
visit[newR][newC] = true;
queue.add(new int[]{newR, newC});
}
}
}
bfs
코드이다.
package baekjoon._2468;
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 {
public static void main(String[] args) {
input();
pro();
}
static int N, max, water;
static int[][] map;
static boolean[][] visit;
static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static void input() {
FastReader fr = new FastReader();
N = fr.nextInt();
map = new int[N][N];
max = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int cur = fr.nextInt();
map[i][j] = cur;
max = Math.max(max, cur);
}
}
}
public static void pro() {
int ans = 0;
for (int i = 0; i <= max; i++) {
water = i;
visit = new boolean[N][N];
int temp = 0;
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if(map[j][k]<=water)continue;
if(visit[j][k])continue;
temp++;
bfs(j, k);
}
}
ans = Math.max(ans, temp);
}
System.out.println(ans);
}
private static void bfs(int r, int c) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{r, c});
visit[r][c] = true;
while (!queue.isEmpty()) {
int[] poll = queue.poll();
int curR = poll[0];
int curC = poll[1];
for (int i = 0; i < 4; i++) {
int newR = curR + dir[i][0];
int newC = curC + dir[i][1];
if(newR < 0 || newC < 0 || newR >= N || newC >= N) continue;
if(visit[newR][newC])continue;
if(map[newR][newC] <= water)continue;
visit[newR][newC] = true;
queue.add(new int[]{newR, newC});
}
}
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in));}
String next(){
while(st == null || !st.hasMoreTokens()){
try{
st = new StringTokenizer(br.readLine());
} catch (IOException e){
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
long nextLong() { return Long.parseLong(next()); }
Double nextDouble() { return Double.parseDouble(next()); }
String nextLine(){
String str = "";
try{
str = br.readLine();
} catch(IOException e){
e.printStackTrace();
}
return str;
}
}
}
처음 문제를 봤을 때 저번에 풀었던 파괴되지않은건물 문제가 생각이 났다. 하지만 이 문제는 누적합을 이용하는 것이 아니라 BFS를 활용한 문제이다. BFS 코드를 외워놨기 때문에 쉽게 풀 수 있는 문제였다.