[백준/C++] 2468번: 안전영역

까다롭지 않은 문제였다. 나도 쉬우니 다들 잘 풀듯,,,

핵심은 비가 아예 안올지도 모른다는 것을 주의해야 한다는 점. 나도 첫제출때 이거땜시 틀렸다. 글고 문제도 약간 이해가 잘 안됐는데 그냥 비오는 높이를 1씩 늘려가면서 연결된 뭉탱이 갯수만 세면 된다.

비 온 높이를 계속 올리다가 4가 되었을 때 map:

비 온 높이를 계속 올리다가 6이 되었을 때 map:

 

반례는 하나만 보면 되는데 

3 3

1 1 1

1 1 1

1 1 1

 

답: 1

 

풀이는 아래와 같이 했음

 

1) 비오는 높이가 0부터 제일높은 건물의 높이까지이다.

2) 높이를 0~최대높이까지 while문으로 돌렸다.

3) while문 내부에서 현재 높이에 대한

   - DFS를 돌려서 뭉탱이의 갯수를 찾는다.

   - 걔를 vector에 push한다.

4) 모든 높이를 탐색했다면 vector에서 제일 큰 값을 출력한다.

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int N;

int map[101][101];
int visit[101][101];
int max_v;

int cnt;

int dx[] = { 1,0,0,-1 };
int dy[] = { 0,1,-1,0 };

void initial() {

	cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = 0;
		}
	}
}

void dfs(int x, int y, int loop) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (map[nx][ny] > loop && visit[nx][ny] == 0) {
			visit[nx][ny] = 1;
			dfs(nx, ny, loop);
		}
	}
}

int main() {

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (i == 0 && j == 0) {
				max_v = map[i][j];
			}
			if (map[i][j] > max_v)max_v = map[i][j];

		}
	}

	vector<int> ans;
	int loop_value = 0;
	while (loop_value <= max_v) {

		initial();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] > loop_value && visit[i][j] == 0) {
					cnt++;
					visit[i][j] = 1;
					dfs(i, j, loop_value);
				
				}
			}
		}
		
		ans.push_back(cnt);
		loop_value++;
	}

	//for (int i = 0; i < ans.size(); i++) {
	//	cout << ans[i] << " ";
	//}


	cout << *max_element(ans.begin(), ans.end());



	return 0;
}