[백준] 1245 농장 관리 + 복습

 

문제

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

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

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

입력

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

출력

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

 

#include<bits/stdc++.h>

using namespace std;
int n, m;
int dy[8] = { -1,-1,0,1,1,1,0,-1 }, dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int visited[100][100], cnt = 0;

void bfs(int a, int b, vector<vector<int>> &mp) {
	queue<pair<int, int>>q;
	q.push({ a,b });
	bool peek = true;  //peek이 true이면 정점이므로 카운트++

	while (!q.empty()) {
		auto top = q.front();
		int y = top.first;
		int x = top.second;
		visited[y][x] = 1;
		q.pop();
		for (int i = 0; i < 8; i++) { //인접의 조건: 상하좌우 뿐만아니라 대각선
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
				if (mp[y][x] < mp[ny][nx]) { //인접한 블록중 더 높은 블록이 있으면 peek가 아님.
					peek = false;
				}
				if (mp[y][x] == mp[ny][nx] && !visited[ny][nx]) { //높이가 같은 인접한 블록은 한번에 처리
					q.push({ ny,nx });
				}
			}
		}
	}
	if(peek)
		cnt++;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int x;
	cin >> n >> m;
	vector<vector<int>>mp(n, vector<int>(m, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> x;
			mp[i][j] = x;
		}
	}
	memset(visited, 0, sizeof(visited));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if(!visited[i][j])
				bfs(i, j, mp);
		}
	}
	cout << cnt;
	return 0;
}

 

골드5 bfs문제입니다.

인접한 같은높이의 블록들을 묶어 peek인지 구분합니다.

중요한건 인접의 조건(상하좌우 + 대각선)입니다. 따라서 배열 dy dx를 8칸으로 늘려야합니다.

 

 

--------------------------------------------------------------------------------------------------------------------------------------------------

복습

 

그런데 굳이 bfs 3번째 인수를 써야하나?

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int>pi;
int N, M, v[101][101], mp[101][101], cnt;
int dy[] = { -1,-1,0,1,1,1,0,-1 }, dx[] = { 0,1,1,1,0,-1,-1,-1 };
bool bfs(int Y, int X) {
	bool flag = true;
	queue<pi>q;
	q.push({ Y,X });
	while (!q.empty()) {
		auto [y, x] = q.front(); q.pop();
		v[y][x] = 1;
		for (int i = 0; i < 8; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && ny < N && nx >= 0 && nx < M) {
				if (mp[y][x] < mp[ny][nx]) flag = false;

				else if (!v[ny][nx] && mp[ny][nx] == mp[y][x]) {
					q.push({ ny,nx });
				}
			}
		}
	}
	return flag;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> mp[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!v[i][j])
				if (bfs(i, j))cnt++;
		}
	}
	cout << cnt;
}

그리고 bfs함수를 bool형으로 만들어서 main에서 답을 카운트하게..만들었습니다