728x90
https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
풀이)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_BJ_2468_안전영역 {
static int[][] map;
static int low=Integer.MAX_VALUE;
static int high=Integer.MIN_VALUE;
static int n;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new int[n][n];
for(int i=0; i<n; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++){
map[i][j] = Integer.parseInt(st.nextToken());
low = Math.min(low, map[i][j]);
high = Math.max(high, map[i][j]);
}
}
int sum=1;
for(int k = low; k<high; k++){
visited = new boolean[n][n];
int temp = 0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(!visited[i][j] && map[i][j]>k){
bfs(i, j, k);
temp++;
}
else if(!visited[i][j] && map[i][j]<=k)
visited[i][j] = true;
}
}
if(sum <= temp) {
sum = temp;
}
}
System.out.println(sum);
}//main
private static void bfs(int x, int y, int level){
Queue<int []> q = new ArrayDeque<>();
visited[x][y] = true;
q.offer(new int[] {x, y});
while(!q.isEmpty()){
int[] cur = q.poll();
for(int i=0; i<4; i++){
int nx = cur[0]+dx[i];
int ny = cur[1]+dy[i];
if(check(nx, ny) && map[nx][ny]>level && !visited[nx][ny]){
visited[nx][ny] = true;
q.offer(new int[] {nx, ny});
}
}
}//while
}//bfs
private static boolean check(int x, int y){
if(x<0 || y<0 || x>=n || y>=n)
return false;
return true;
}//check
}이 문제는 완탐과 bfs를 이용하면 간단한 문제다!!
전체 지도를 입력받고, bfs를 이용해서 잠기지 않은 부분을 탐색한다!
이때, visited 배열을 이용해서 방문 처리를 한다.(이때, 잠긴 부분도 방문 처리를 해야 편하다!)
먼저 맵에서 가장 작은 수위와 높은 수위를 체크한 후 for문을 돌린다.
그리고 전체 맵을 완전 탐색 하면서 방문하지 않았고, 잠기지 않으면 다시 bfs를 한다.
이때, bfs를 수행한다는 것은 적어도 하나의 잠기지 않은 땅이 생기는 것이므로 땅의 개수를 추가해주면 된다.
그리고 하나의 탐색이 끝날때마다 가장 큰 값으로 교체하면 끝!
728x90
'코테 > 백준' 카테고리의 다른 글
| 백준 2583 영역 구하기(JAVA) (0) | 2023.04.20 |
|---|---|
| 백준 10951 A+B - 4(JAVA) (0) | 2023.04.18 |
| 백준 1715 카드 정렬하기(JAVA) (0) | 2023.04.11 |
| 백준 10844 쉬운 계단 수(JAVA) (0) | 2023.04.06 |
| 백준 1946 신입 사원(JAVA) (0) | 2023.04.06 |