문제링크
https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
DFS문제였다.
1. 2차원 배열에 강수량 입력받기
2. 최대 강수량 max값에 저장하기
3. safe_zone은 높이를 저장하는 변수다 0부터 max값까지 while문으로 반복하며 확인해준다.
- safeZone 배열에 현재 높이 이하인 부분은 false로 현재 높이 초과인 부분은 true 설정해준다.
- safeZone배열을 돌면서 현재 방문한 곳이 방문하지 않은 곳 && 안전지역이면 dfs함수 (find())를 통해 확인하여준다.
- find()에서는 현재 입력받은 지점을 기준으로 사방향을 탐색하며 안전지역을 탐색한다.
(safeZone[nx][ny]부분이 true인 곳만 탐색) - find() 함수가 끝나면 1개의 안전지역이 설정?된다.
※ 참고한 예외
https://www.acmicpc.net/board/view/69962
글 읽기 - 강수량은 0에서 부터 체크하는게 맞을듯
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
처음에 강수량을 min~max까지 설정하여 탐색했는데
3
2 2 2
2 2 2
2 2 2
output : 1
이 나와야하는데 2부터 탐색하므로 0이 나오는 경우가 발생했다.
강수량은 0부터,,
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
package BOJ;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_2468 {
static int N;
static int map[][];
static boolean isVisited[][],safeZone[][];
static int dx[] = {0,0,-1,1};
static int dy[] = {-1,1,0,0};
static int result;
static int max = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
StringTokenizer st;
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(max < map[i][j]) max = map[i][j];
}
}
int safe_zone = 0;
while(safe_zone<=max){
safeZone = new boolean[N][N];
isVisited = new boolean[N][N];
//min~max까지 숫자 올리면서 check해보기
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){ //물에 잠기는 지점을 false로 표시
if(map[i][j] > safe_zone) safeZone[i][j] = true;
}
}
int res = 0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(safeZone[i][j] && !isVisited[i][j]){
//물에 잠기지 않은 곳 && 방문하지 않은 곳이면 isVisited[i][j] = true;
find(i,j); //dfs로 찾기
res++;
}
}
}
result = Math.max(res,result);
safe_zone++;
}
System.out.println(result);
}
private static void find(int i,int j) {
//현재 입력받은 지점 기준 4방향 탐색
for(int d=0;d<4;d++){
int nx = i + dx[d];
int ny = j + dy[d];
//범위 벗어나거나 방문했던 곳이면 지나치기
if(nx<0 || ny<0 || nx>=N || ny>=N || isVisited[nx][ny]) continue;
if(safeZone[nx][ny]){
isVisited[nx][ny] = true;
find(nx,ny);
}
}
}
}
|
cs |
|
|
|
'알고리즘 > 백준' 카테고리의 다른 글
| [JAVA]백준_2750_수 정렬하기 (0) | 2021.06.24 |
|---|---|
| [JAVA]백준_10773_제로 (0) | 2021.06.24 |
| [JAVA]백준_10814_나이순정렬 (0) | 2021.06.23 |
| [JAVA]백준_14425_문자열집합 (0) | 2021.06.23 |
| [JAVA]백준_20053_최소,최대2 (0) | 2021.06.23 |
