백준 2667번 단지번호붙이기 (BFS)

백준 2667번 단지번호붙이기를 풀어보자.

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

2667번: 단지번호붙이기

 

 

이전에 풀었던 토마토 문제와 같이 전형적인 맵형태의 BFS로 풀 수 있는 문제이다.

다만, 연결되어 있는 부분의 개수(단지 개수)를 구해야 해서 BFS를 여러번 호출해야 한다.

 

처음에 맵에 해당하는 입력값을 받고 반복문을 수행하면서 입력값이 1이면서 방문하지 않은곳을 BFS로 호출한다.

그럼 아래 그림처럼 첫번째 BFS를 호출할때는, 회색영역에 해당하는 부분을 모두 체크할 것이다.

 

BFS를 호출하면 이전에 토마토 문제에서 구현했던 것처럼, 현재 값을 q에 넣고 visited 값을 1로 바꿈으로써 방문표시를 한다.

다음으로 반복문을 통해 q가 비어질 때까지, 현재 값을 q에서 pop하고 상하좌우 값인 nx, ny값을 구한다.

그리고 맵 값이 1이면서 방문하지 않은 값을 탐색하면서 q에 넣고 visited 값을 변경한다.

마지막으로 구해야하는 cnt 값을 증가시켜서 ans라는 vector 값에 넣게 된다.

vector 값을 사용한 이유는 단순하게 문제에서 요구하는 값을 오름차순으로 정렬해서 호출하기 위함이다. (벡터에서 정렬을 자체 제공하므로..)

 

그러면 ans 벡터 값에는 1단지에 해당하는 값 7, 2단지에 해당하는 값 8, 3단지에 해당하는 값 9가 들어가게 된다.

먼저 백터의 size인 3을 호출해주고, sort로 정렬한 뒤, for문을 수행하며 각 벡터에 들어가있는 값을 출력하면 된다.

 

 

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

string map[25];
int visited[25][25];

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

vector<int> ans;

void bfs(int x, int y) {
	int cnt = 1;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visited[x][y] = 1;
	
	while (!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
				continue;
			}

			if (map[nx][ny] == '1' && visited[nx][ny] == 0) {
				q.push(make_pair(nx, ny));
				visited[nx][ny] = 1;
				cnt++;
			}
		}
	}

	ans.push_back(cnt);
}

int main(void) {

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> map[i];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == '1' && visited[i][j] == 0) {
				bfs(i, j);
			}			
		}
	}

	cout << ans.size() << "\n";
	
	sort(ans.begin(), ans.end());

	for (int i = 0; i < (int)ans.size(); i++) {
		cout << ans[i] << "\n";
	}

	return 0;
}