[백준][C++]2667번. 단지번호 붙이기

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

 

그래프를 입력받고 그래프 전체를 순회하는데 방문하지 않았고 1이라면 집이 있기 때문에 여기서부터 BFS방식으로 순회하면서 더 이어진 주택이 없을 때까지 순회한다. 그리고 이 과정에서 들린 집개수를 카운트해서 반환해주면 된다.

 

정답코드

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

using namespace std;

int n;
int BFS(int x,int y);
vector<vector<int>> house;
vector<vector<bool>> visited;
int main()
{
	cin >> n;

	house.resize(n, vector<int>(n));
	visited.resize(n, vector<bool>(n,false));

	//그래프 입력
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			char c;
			cin >> c;
			//문자열-> 숫자
			house[i][j] = c - '0';
		}
	}

	vector<int> answer;

	//그래프 순회
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!visited[i][j] && house[i][j] == 1)
			{
				int h_cnt = BFS(i, j);
				answer.push_back(h_cnt);
			}
		}
	}
	
	//오름차순 정렬
	sort(answer.begin(), answer.end());
	cout << answer.size() << "\n";
	for (int i = 0; i < answer.size(); i++)
	{
		cout << answer[i] << "\n";
	}
}

int BFS(int x,int y)
{
	//상하좌우
	int nx[4] = { -1,1,0,0 };
	int ny[4] = { 0,0,-1,1 };

	queue<pair<int, int>> q;


	q.push({ x,y });
	visited[x][y] = true;

	int cnt = 1;

	//현재위치에서 이어져 있는 주택이 있으면 연결
	while (!q.empty())
	{
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int next_x = cur_x + nx[i];
			int next_y = cur_y + ny[i];

			if (next_x >= 0 && next_x < n && next_y>=0 && next_y < n)
			{
				if (house[next_x][next_y] == 1 && !visited[next_x][next_y])
				{
					q.push({ next_x,next_y });
					visited[next_x][next_y] = true;
					cnt++;
				}
			}
		}
	}

	return cnt;	
}