✉️문제
https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
📝 접근
DFS, BFS를 이용하여 문제 풀이가 가능하다. 필자는 DFS를 이용했다. (미로 찾기처럼 뻗어나가는 문제는 DFS를 이용한 풀이를 좋아하는 편이다)
🗝 문제풀이
1. 높이가 0 ~ 100 범위일 때 안전한 지역을 찾고, DFS를 이용하여 안전 지역의 범위를 체크한다.
⚠️ 높이가 1 ~ 100 범위이기 때문에 h를 1로 둘 수 있는데 1부터 시작하게 되면 아무 지역도 물에 잠기지 않을 수 있다는 조건을 체크하지 못한다.
for(int h = 0; h <= maxHeight; h++) {
ch = new boolean[n][n];
int cnt = 0;
for(int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!ch[i][j] && area[i][j] > h) {
DFS(i, j, h);
cnt++;
}
}
}
answer = Math.max(answer, cnt);
}
[최종 코드]
package baekjoon;
import java.util.Scanner;
public class B2468 {
static int[][] area;
static boolean[][] ch;
static int[] dx = {-1, 0, 0, 1}, dy = {0, -1, 1, 0};
static int n, answer = Integer.MIN_VALUE, maxHeight = Integer.MIN_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
area = new int[n][n];
// 지역값 입력 받기
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
area[i][j] = sc.nextInt();
maxHeight = Math.max(maxHeight, area[i][j]);
}
}
// 높이는 1 ~ 100 범위이지만,
// 1부터 시작하는 경우에 아무 지역도 물에 잠기지 않을 수 있다는 조건을 만족하지 못한다.
for(int h = 0; h <= maxHeight; h++) {
ch = new boolean[n][n];
int cnt = 0;
for(int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!ch[i][j] && area[i][j] > h) {
DFS(i, j, h);
cnt++;
}
}
}
answer = Math.max(answer, cnt);
}
System.out.println(answer);
}
private static void DFS(int x, int y, int h) {
ch[x][y] = true;
for(int i = 0; i < dx.length; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (!ch[nx][ny] && area[nx][ny] > h) {
DFS(nx, ny, h);
}
}
}
}
}