C++ / 백준 / 1245 / 농장 관리

문제

 

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

1245번: 농장 관리

문제풀이

 

문제를 제대로 안 봐서 조금 헤맸다.

인접한 격자는 상, 하, 좌, 우의 네 방향이 아닌 대각선까지 포함하여 총 여덟 방향이다.

그리고 산봉우리는 하나의 칸일 수도 있고 여러 칸일 수도 있다.

산봉우리 격자들은 모두 같은 높이여야 하고, 그 외의 칸들은 산봉우리의 높이보다 작아야 한다.

 

우선순위 큐를 이용해 높이 기준으로 내림차순 하게끔 cmp함수를 작성했다.

그리고 BFS를 통해 인접한 칸들을 탐색한다.

 

	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			cin >> board[y][x];
			if (board[y][x] > 0) peak.push({ y,x });
		}
	}

	int answer(0);

	while (!peak.empty()) {
		int y = peak.top().first;
		int x = peak.top().second;
		peak.pop();
		if (visited[y][x] == true) continue;
		++answer;
		BFS(y, x);
	}

메인 문이다.

산봉우리의 높이가 0인 칸들은 무시해도 되므로 1 이상인 위치만 peak이라는 우선순위 큐에 저장한다.

우선순위 큐가 빌 때까지 해당 칸이 방문한 적이 없으면 BFS함수를 실행한다.

 

void BFS(int y, int x) {
	int max = board[y][x];
	queue<pii>q;
	q.push({ y,x });

	visited[y][x] = true;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int idx = 0; idx < 8; ++idx) {
			int ny = y + dy[idx];
			int nx = x + dx[idx];
			if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
			if (visited[ny][nx] == true) continue;
			if (board[ny][nx] > max) continue;
			if (board[ny][nx] == 0) continue;
			if (board[ny][nx] > board[y][x]) continue;
			visited[ny][nx] = true;
			q.push({ ny,nx });
		}
	}
}

인자로 받은 칸이 산봉우리의 높이가 된다.

다음 칸을 탐색할 때는 범위를 벗어나면 안 되고, 방문한 적이 없어야 한다.

그리고 해당 칸의 높이가 산봉우리보다 높으면 안 되고,

0이면 안되고,

이전칸 보다 높으면 안 된다.

이러면 높이가 높은 곳부터 낮은 곳 순서로 탐색하게 된다.

 

코드

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

int dy[8] = { -1,-1,-1,0,0,1,1,1 };
int dx[8] = { -1,0,1,-1,1,-1,0,1 };
vector<vector<int>>board;
vector<vector<bool>>visited;
int N, M;

struct compare {
	bool operator()(pii& c1, pii& c2) {
		return board[c1.first][c1.second] < board[c2.first][c2.second];
	}
};

priority_queue<pii, vector<pii>, compare>peak;

void BFS(int y, int x) {
	int max = board[y][x];
	queue<pii>q;
	q.push({ y,x });

	visited[y][x] = true;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int idx = 0; idx < 8; ++idx) {
			int ny = y + dy[idx];
			int nx = x + dx[idx];
			if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
			if (visited[ny][nx] == true) continue;
			if (board[ny][nx] > max) continue;
			if (board[ny][nx] == 0) continue;
			if (board[ny][nx] > board[y][x]) continue;
			visited[ny][nx] = true;
			q.push({ ny,nx });
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;
	board = vector<vector<int>>(N, vector<int>(M, 0));
	visited = vector<vector<bool>>(N, vector<bool>(M, false));

	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			cin >> board[y][x];
			if (board[y][x] > 0) peak.push({ y,x });
		}
	}

	int answer(0);

	while (!peak.empty()) {
		int y = peak.top().first;
		int x = peak.top().second;
		peak.pop();
		if (visited[y][x] == true) continue;
		++answer;
		BFS(y, x);
	}

	cout << answer;
}