[BOJ / C++] 영역 구하기 (BFS)

문제 링크:

https://www.acmicpc.net/problem/2583

 

1. 코드

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

int m, n, k;

vector<vector<int>> board(102, vector<int>(102, 1));
vector<vector<bool>> vis(102, vector<bool>(102, false));

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

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

	cin >> m >> n >> k;

	for (int i = 0; i < k; i++) {
		int x1, y1, x2, y2;
		cin >> y1 >> x1 >> y2 >> x2;
		
		for (int p = x1; p < x2; p++) {
			for (int q = y1; q < y2; q++) {
				board[p][q] = 0;
			}
		}
	}

	int num = 0;
	vector<int> areaList;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (board[i][j] == 0 || vis[i][j] == true) continue;

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

			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 >= m || ny < 0 || ny >= n) continue;
					if (vis[nx][ny] == true || board[nx][ny] == 0) continue;

					Q.push({nx, ny});
					vis[nx][ny] = true;
					area++;
				}
			}
			areaList.push_back(area);
		}
	}

	sort(areaList.begin(), areaList.end());
	
	cout << num << '\n';
	for (int i: areaList) {
		cout << i << ' ';
	}

}

 

2. 분석

수학 좌표 형식으로 입력받아서 x, y가 어떤 것을 나타내는 지 헷갈릴 수 있다. 이 부분만 신경쓰면 전형적인 bfs 문제 풀이와 동일하다. 나는 주로 x를 행, y를 열로 생각해서 입력을 자체를 거꾸로 받았다.

 

board에서 색칠되지 않은 곳을 기본값으로 1로 표시했고, 색칠된 곳을 골라서 0으로 표시한 후 bfs를 돌리면 된다.

 

3. 시간복잡도

최악의 경우 board 전체를 한번씩 방문하여 m*n이고 bfs에서 각 칸은 최대 한번씩만 queue에 들어간다. (vis 배열로 배제) 따라서 시간복잡도는 O(mn)이다.