[BOJ / C++] 안전 영역 (BFS)

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

 

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int n;
	cin >> n;

	vector<vector<int>> board(n, vector<int>(n, 0));
	
	int maxH = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			maxH = max(board[i][j], maxH);
		}
	}
	
	int maxSafe = 0;
	for (int height = 0; height <= maxH; height++) {  // height = 0부터 height <= maxH까지 확인 중요
		vector<vector<bool>> vis(n, vector<bool>(n, false));

		int num = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i][j] <= height || vis[i][j]) continue;

				queue<pair<int, int>> Q;
				Q.push({i, j});
				vis[i][j] = true;
				num++;

				while (!Q.empty()) {
					auto cur = Q.front(); Q.pop();
					int x = cur.first;
					int y = cur.second;

					for (int dir = 0; dir < 4; dir++) {
						int nx = x + dx[dir];
						int ny = y + dy[dir];

						if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
						if (board[nx][ny] <= height || vis[nx][ny]) continue;

						Q.push({nx, ny});
						vis[nx][ny] = true;
					}
				}
			}
		}
		maxSafe = max(num, maxSafe);
	}

	cout << maxSafe;
}

 

2. 분석

 

문제에 보면 높이는 1이상 100 이하의 정수라고 되어있다. 그래서 처음에 height = 1 .. maxHeight까지 반복하며 bfs를 진행했다. 그러면 한 40% 정도에서 중간에 '틀렸습니다' 판정을 받는다. 계속 찾아보다가 문제 아래에서 이런 힌트를 발견했다.

즉, height = 0 부터 시작해야한다는 소리이다. 해당 edge case를 검출해내는 test case가 포함되어있는 모양이다.  이 부분에 주의해서 문제를 풀면 된다.

 

3. 시간복잡도

최대 n = 100이고, height 최대도 100이다. 시간복잡도는 O((maxH+1) * n^2)이고, 10^6 정도 이다. 시간제한 1초는 cpp가 10^7 ops/sec 안에 대충 들어오면 된다. 따라서 세제곱 모양이어도 n과 maxH가 충분히 작으므로 만족하게 된다..