글 읽기 - 문제 접근 방법을 모르겠습니다..

nlkey2022 5년 전 0

가장 가장자리 if (i == 1 || j == 1 || i == h || j == w)

부분은 무조건 웅덩이가 아닌것을 감안하면

웅덩이가 아닌 지역과 인접한 부분 중에 보다 높거나 같은 지역은 무조건 웅덩이가 아니므로 a[here.first][here.second] <= a[nx][ny]

bfs로 생각했으나..

9 12

5 5 5 5 5 5 5 5 5

5 2 2 2 2 2 2 2 5

5 2 9 9 9 9 9 2 5

5 2 9 6 6 6 9 2 5

5 2 9 9 9 9 9 2 5

5 2 2 2 2 2 2 2 5

5 5 5 5 5 5 5 5 5

이러한 반례가 있네요.. (웅덩이 안에 웅덩이)

어떻게 접근해야할지 모르겠습니다

#include<iostream>
#include<queue>
#include<cstring>
#include<limits.h>
using namespace std;
int h, w, a[1001][1001];
bool check[1001][1001], visited[1001][1001];

int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int main() {
	cin >> w >> h;
	for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) cin >> a[i][j];
	// check 배열은 물이 아닌 지역을 의미한다.
	// 배열의 첫과 마지막 행,열은 모두 물이 아닌 지역이므로 무조건 물이 아닌지역(land)로 본다.
	queue<pair<int, int>> land;
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++)
			if (i == 1 || j == 1 || i == h || j == w) {
				land.push(make_pair(i, j));
				check[i][j] = true;
			}
	// bfs, land는 자기 위치보다 작거나 높은 지역은 물 웅덩이가 될 수 없으므로 
	while (!land.empty()) {
		auto here = land.front();
		land.pop();
		for (int k = 0; k<4; k++) {
			int nx = here.first + dx[k];
			int ny = here.second + dy[k];
			if ((1 <= nx && nx <= h) && (1 <= ny && ny <= w) && !check[nx][ny] && a[here.first][here.second] <= a[nx][ny]) {
				land.push(make_pair(nx, ny));
				check[nx][ny] = true;
			}
		}
	}
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++)
			visited[i][j] = check[i][j];
	int ans = 0;
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++)
			if (!visited[i][j]) {
				// bfs
				int mini = 10e9;
				queue<pair<int, int>> q;
				vector<int> v;
				v.push_back(a[i][j]);
				q.push(make_pair(i,j));
				visited[i][j] = true;
				while (!q.empty()) {
					auto here = q.front();
					q.pop();
					for (int k = 0; k < 4; k++) {
						int nx = here.first + dx[k];
						int ny = here.second + dy[k];
						if ((1 <= nx && nx <= h) && (1 <= ny && ny <= w)){
							if (!check[nx][ny] && !visited[nx][ny]) {
								q.push(make_pair(nx,ny));
								v.push_back(a[nx][ny]);
								visited[nx][ny] = true;
							}
							else if(check[nx][ny]){
								mini = min(mini,a[nx][ny]);
							}
						}
					}
				}
				cout << mini << endl;
				int temp = v.size();

				for (int k = 0; k < v.size(); k++) {
					if (v[k] >= mini) temp--;
				}
				ans = max(temp, ans);
			}
	cout << ans;			
}