BOJ - 1245 - 농장 관리
문제
문제
농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.
산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 “인접하다”의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.
문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.
입력
첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수이다.
출력
첫째 줄에 산봉우리의 개수를 출력한다.
구현
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
#include <iostream>
using namespace std;
// map
int n, m;
int map[104][104];
bool visited[104][104];
// joy
int dy[] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dx[] = {0, 1, 0, -1, 1, -1, -1, 1};
// ans
int ans = 0;
bool peak;
void dfs(int y, int x)
{
visited[y][x] = 1;
for(int i=0; i < 8; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || nx < 0 || ny >= n || nx >= m)
continue;
if(map[ny][nx] > map[y][x])
peak = 0;
if(map[ny][nx] == map[y][x] && !visited[ny][nx])
dfs(ny, nx);
}
}
int main()
{
cin >> n >> m;
for(int i=0; i < n; i++)
for(int j=0; j < m; j++)
cin >> map[i][j];
for(int i=0; i < n; i++)
for(int j=0; j < m; j++)
if(!visited[i][j] && map[i][j])
{
peak = 1;
dfs(i, j);
if(peak)
ans++;
}
cout << ans << endl;
return 0;
}
SOL
1
2
3
4
5
6
// 봉우리가 아닐 경우
if(map[ny][nx] > map[y][x])
peak = 0;
// 같은 높이고, 방문하지 않았을 경우
if(map[ny][nx] == map[y][x] && !visited[ny][nx])
dfs(ny, nx);