백준 2468 안전 영역

문제 링크 : https://www.acmicpc.net/problem/2468

※선행해야 할 알고리즘 : BFS/DFS

Algorithm : 그래프를 입력받아 높이에 따라 안전한 영역의 군집 개수 중 가장 큰 값을 출력해라.

1. 먼저, 풀기 전 문제를 확실히 이해 할 필요가 있다.

입력 예제를 봤을 때,

6 8 2 6 2

3 2 3 4 6

6 7 3 3 2

7 2 5 3 6

8 9 5 2 7

이런 식으로 있는데 출력은 5인 것을 확인 할 수 있을 것이다.

그 이유는

높이가 1이하인 모든 영역에 물이 차올랐을 때,

높이가 2이하인 모든 영역에 물이 차올랐을 때,

.

.

.

높이가 100이하인 모든 영역에 물이 차올랐을 때,

를 기준으로 계산 후 영역이 제일 많았던 높이가 4일 때의 군집의 개수인 5가 되는 것이다.

2. 1. 을 이해 했다면 가장 먼저 해야할 것은 행렬 중 max 값을 찾아주는 것이다.

3. 찾은 max값을 통해 1씩 줄여나가며 

   군집이 1이면서, q에 데이터가 삽입된 횟수가 n*n번이면(모든 원소를 다 들렸기 때문에)

   min값을 발견한 것이므로 해당 데이터까지만 반복하여 군집의 개수를 vector에 삽입한다.

4. 반환된 vector의 최대값을 출력하면 된다.

5. 1~4를 queue를 활용하여 T번 반복하여 BFS를 진행하면 다음과 같다.

//kuklife.tistory.com #include<iostream> #include<algorithm> #include<vector> #include<queue> using namespace std; int n; int dx[] = { 1, -1, 0, 0 }; int dy[] = { 0, 0, 1,-1 }; pair<int, int> search(vector<vector<int>> G, int max) { for (int i = 0; i < G.size(); i++) for (int j = 0; j < G[i].size(); j++) if (G[i][j] > max) return { i,j }; return { -1, -1 }; } int sol(vector<vector<int>> G, int max, int &count) { int result = 0; while (1) { queue<pair<int, int>> q; auto s = search(G, max); if (s.first == -1 && s.second == -1) break; q.push({ s.first, s.second }); result++; while (!q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); if (y >= 0 && y < n && x >= 0 && x < n && G[y][x] > max) { G[y][x] = max; count++; for (int i = 0; i < 4; i++) { int now_y = y + dy[i]; int now_x = x + dx[i]; q.push({ now_y, now_x }); } } } } return result; } int main() { cin >> n; vector<vector<int>> G(n); vector<int> result; int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int x; cin >> x; G[i].push_back(x); } } vector<int> max_vector; for (int i = 0; i < n; i++) max_vector.push_back(*max_element(G[i].begin(), G[i].end())); int max = *max_element(max_vector.begin(), max_vector.end()); for (int i = max; i >= 1; i--) { int result_element = sol(G, i, count); if (result_element == 1 && count >= n * n) break; else result.push_back(result_element); } max = *max_element(result.begin(), result.end()); if (max == 0) cout << 1 << endl; else cout << max << endl; return 0; }