[백준/C++] 안전 영역_2468

📝 문제

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;
}

📌 해결방법

1. 비의 양을 지역 배열에서 최소부터 최대까지로 설정(비가 안올 수 있음 주의!)
2. 지역 높이가 비의 양보다 높을 때 안전지역 +1

✔ 느낀 점

dfs와 bfs는 국밥처럼 든든하다. 코테도 이랬으면 좋겠다😂