[BOJ / C++] 단지번호붙이기 (BFS)

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

 

1. 코드

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

int n;

vector<vector<int>> board(30, vector<int>(30, 0));
vector<vector<bool>> vis(30, vector<bool>(30, 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);

	// input
	cin >> n;

	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < n; j++) {
			board[i][j] = str[j] - '0';
		}
	}
	vector<int> areaList;

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

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

			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] == 0 || vis[nx][ny]) continue;

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

	sort(areaList.begin(), areaList.end());
	
	// output
	cout << areaList.size() << '\n';
	for (int a: areaList) {
		cout << a << '\n'; 
	}
}

 

2. 분석

vis 배열에 방문여부를 잘 체크하는 것에 주의한다. 특별할 것이 없는 전형적인 bfs이다.

 

입력받을 때 board에는 int로 저장하고 싶으므로 string으로 입력받아 하나씩 접근해 str[j] - '0'으로 char to int type casting을 해준다. 문자 '0'의 ASCII code가 48이므로, '1' - '0' 하면 49 - 48 = 1로 쉽게 변환 된다.

string str;  // "101101"
cin >> str;
for (int j = 0; j < n; j++) {
	board[i][j] = str[j] - '0';
}

 

3. 시간복잡도 

n*n 정사각형 배열을 순회하고, 모든 칸은 한번씩만 방문한다. 큐에도 최대 한번씩만 들어간다. 따라서 시간복잡도는 O(n^2)이 된다.