[BOJ/Gold 5] 백준 1245 농장 관리(C++)

문제 링크

https://www.acmicpc.net/problem/1245

1245번: 농장 관리

문제

농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.

산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

입력

첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 산봉우리의 개수를 출력한다.

예제 입력 1

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

예제 출력 1

3

알고리즘 분류

• 그래프 탐색

풀이

자신보다 높은 높이의 칸을 만나면 Flag를 false로 하고, 그렇지 않으면 큐에 계속 칸의 좌표를 push하는 것이다.

Flag가 true고 높이가 최소 높이보다 높으면 산봉우리의 개수를 1개 추가한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 105
#define LL long long
#define INF 2e9

using namespace std;
int N, M;
int minHeight = INF;
int MAP[MAX][MAX];
bool visited[MAX][MAX];
int moveY[8] = { -1,-1,0,1,1,1,0,-1 };
int moveX[8] = { 0,1,1,1,0,-1,-1,-1 };
int answer = 0;

bool BFS(int Y, int X, int H) {
	queue<pair<int, int> > Q;
	visited[Y][X] = true;
	bool Flag = true;
	Q.push(make_pair(Y, X));

	while (!Q.empty()) {
		int CurY = Q.front().first;
		int CurX = Q.front().second;
		Q.pop();

		for (int i = 0; i < 8; i++) {
			int nextY = CurY + moveY[i];
			int nextX = CurX + moveX[i];
			if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < M)) {
				if (MAP[nextY][nextX] > H) {
					Flag = false;
				}
				else if ((!visited[nextY][nextX]) && (MAP[nextY][nextX] == H)) {
					visited[nextY][nextX] = true;
					Q.push(make_pair(nextY, nextX));
				}
			}
		}
	};

	return Flag;
}

int main() {
	FIRST
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> MAP[i][j];
			minHeight = min(minHeight, MAP[i][j]);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!visited[i][j]) {
				if (BFS(i, j, MAP[i][j]) && (MAP[i][j] > minHeight)) {
					answer++;
				}
			}
		}
	}
	cout << answer << "\n";

	return 0;
}