https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어
www.acmicpc.net
|
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
|
#include<stdio.h>
#include<string.h>
#define NSIZE 100
using namespace std;
int N, input[NSIZE][NSIZE];
int chk[NSIZE][NSIZE];
int Max = 0x80000000;
int Min = 0x7fffffff;
int ret = 0x80000000;
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
void init() {
Max = 0x80000000;
Min = 0x7fffffff;
ret = 0x80000000;
memset(input, 0, sizeof(input));
memset(chk, 0, sizeof(chk));
scanf("%d", &N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &input[i][j]);
if (Min > input[i][j]) Min = input[i][j];
if (Max < input[i][j])Max = input[i][j];
}
}
}
void dfs(int y, int x,int num) {
for (int dir = 0; dir < 4; dir++) {
int ny = y + dy[dir]; int nx = x + dx[dir];
if (0 <= ny && ny < N && 0 <= nx && nx < N) {
if (input[ny][nx] > num && chk[ny][nx] == 0) {
chk[ny][nx] = 1;
dfs(ny, nx,num);
}
}
}
}
int cntzero(int chk[NSIZE][NSIZE]) {
int cnt = 0;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (chk[y][x] == 0)cnt++;
}
}
return cnt;
}
void summerwater() {
for (int num = Min; num <= Max; num++) {
memset(chk, 0, sizeof(chk));
int cnt = 0;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (input[y][x] > num&&chk[y][x]==0) {
cnt++;
chk[y][x] = 1;
dfs(y, x,num);
}
}
}
if (ret < cnt)ret = cnt;;
}
}
int main(void) {
init();
summerwater();
if (ret == 0)ret = 1;
printf("%d\n", ret);
}
|
정말 쉽게 생각할 수 있는 것이 문제를 보면 지형의 높이 가 주어져있고,
비가 만약에 4이하인 지점을 잠길 수 있다면 결국은 우리가 찾아야 하는 것은 5 이상인 곳입니다.
그래서 플러드 필을 사용하여 즉 dfs를 이용하여 4라면 5이상이것을 dfs로 돌리면
이런 식으로 구현이 되어야 맞게 구현한 것입니다.
결국은 플러드 필을 사용할 줄 아느냐가 포인트였는데 우선 저런 문제는 dfs 하는 게 쉽고 여기서 비의 크기를 선별할 때
1-100까지 해봐도 되지만
조금 더 빠를 수 있게 배열의 숫자에 최솟값과 최댓값을 뽑아
예를 들어 최솟값이 2이고 최댓값이 7이라고 하면 2-7까지만 반복문을 돌려 dfs로 저런 영역이 몇 개인지
확인해주면 됩니다. 물론 중복 없이 숫자를 배열에 넣고 해도 되지만 그게 오히려 더 오래 걸릴 수 있으니 간단히
다른 방법으로도 해보세요.
사람마다 하는 방식이 다르기 때문에 다양한 방법으로 구현해 보시면 도움이 많이 됩니다.
그 속에서 이런 소스로는 짜면 안 되겠구나를 느낄 수 있기 때문입니다.
dfs를 돌리는 것은 아주 기초이기 때문에 설명은 생각하겠습니다.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 2638 치즈 (0) | 2019.09.17 |
|---|---|
| 백준 1726 로봇 (0) | 2019.09.17 |
| 백준 1938 통나무 옮기기 (0) | 2019.09.11 |
| 백준 3987 보이저 1호 (0) | 2019.09.09 |
| 백준 2174 로봇 시뮬레이션 (0) | 2019.09.09 |
댓글