[그래프] BOJ 2667번 단지번호붙이기

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

2667번: 단지번호붙이기

- 문제파악

NxN 배열이 주어지고 배열 내에 값은 0과 1이 주어진다. 1이 상하좌우로 붙어있다면 인접해있다고 한다. 1이 인접한 그룹의 개수(단지의 개수)와 그룹내의 1의 개수(단지 내 건물 개수)를 출력하라

 

-정답

BFS로 풀이했다.

처음에 큐에 푸쉬하는 것도 체크해야한다.

 

#include "bits/stdc++.h"

using namespace std;

int arr[26][26];
int check[26][26];

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

	int n;
	cin >> n;

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

	string input;

	for (int i = 0; i < n; i++)
	{
		cin >> input;
		int j = 0;
		for (auto c : input)
		{
			int a = c - 0x30;
			check[i][j] = arr[i][j] = a;
			j++;
		}
	}

	queue<pair<int,int>> q;
	vector<int> vec;
	int cnt = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cnt = 0;

			if (arr[i][j] && check[i][j])
			{
				q.push({ i,j });
				check[i][j] = 0;
				while (!q.empty())
				{
					int qx = q.front().first;
					int qy = q.front().second;
					q.pop();
					cnt++;

					for (int k = 0; k < 4; k++)
					{
						int nx = qx + dx[k];
						int ny = qy + dy[k];

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

						if (arr[nx][ny] && check[nx][ny])
						{
							check[nx][ny] = 0;
							q.push({ nx ,ny });
							
						}
					}

					
				}

							
			}

			if (cnt)
				vec.push_back(cnt);
		}
	}


	cout << vec.size() << "\n";

	sort(vec.begin(), vec.end());

	for (auto a : vec)
		cout << a << "\n";
	

}