https://www.acmicpc.net/problem/2468
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n;
int arr[100][100];
int visited[100][100] = { 0, };
int ans = 1;
void reset() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visited[i][j] = 0;
}
}
}
void bfs(int r, int c, int h) {
queue<pair<int, int>> q;
visited[r][c] = 1;
q.push(make_pair(r, c));
int dr[] = { 0, 0, -1, 1 };
int dc[] = { 1, -1, 0, 0 };
while (!q.empty()) {
int row = q.front().first;
int col = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nRow = row + dr[i];
int nCol = col + dc[i];
if (nRow < 0 || nCol < 0 || nRow >= n || nCol >= n || visited[nRow][nCol]) continue;
if (arr[nRow][nCol] <= h) {
continue;
}
visited[nRow][nCol] = 1;
q.push(make_pair(nRow, nCol));
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
int MAX = 0;
for (int i = 0; i < n; i++) {
MAX = *max_element(arr[i], arr[i] + n);
}
for (int water = 1; water < MAX; water++) {
// 비의 양 하나씩 dfs or bfs
int cnt = 0;
reset();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] > water && visited[i][j] == 0) { // 안전지역
bfs(i, j, water);
cnt += 1;
}
}
}
if (ans < cnt) {
ans = cnt;
}
}
cout << ans;
return 0;
}
dfs와 bfs는 국밥처럼 든든하다. 코테도 이랬으면 좋겠다😂
이제 그래프는 마스터하셨네요 너무 부러워요,,