[백준]Baekjoon2667(DFS,BFS)

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

BFS를 사용하여 문제를 풀어보았다.

반복문을 돌며 만약 해당 좌표에 아파트가 있다면 

그 좌표를 중심으로 BFS를 수행하였다. 

그리고 숫자를 세면서 검사한 좌표를 모두 0으로 바꿔주어 중복하여 세지 않도록 하였다.

이런식으로 하게되면 BFS를 한번 돌렸을 때 해당 단지의 숫자를 알게되며

그 단지의 좌표는 모두 0이 되기 때문에 한번 검사했던 단지의 아파트를 다시 검사하지 않게 된다.

이런식으로 끝까지 검사를 수행하면 원하는 답을 얻어낼 수 있다.

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

using namespace std;

int arr[25][25];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int N;
int BFS(int x,int y) {
	queue<pair<int, int>> q;
	int cnt = 1;
	q.push(make_pair(x, y)); //맨 처음의 X,Y를 큐에 삽입
	arr[x][y] = 0; // 큐에 들어간 좌표는 해당 아파트를 확인한 것이기
	//떄문에 0으로 바꿔준다.
	while (!q.empty()) //큐가 빌 때까지
	{
		x = q.front().first; //큐의 맨 앞에있는 좌표의 x
		y = q.front().second; //큐의 맨 앞에있는 좌표의 y
		q.pop(); //x와 y를 꺼냈기 때문에 큐에서 해당 좌표 제거
		for (int i = 0; i < 4; i++) { //x와 y의 상하좌우에대한 검사
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < N && ny >= 0 && ny < N) { 
				if (arr[nx][ny] != 0) { //만약에 좌표가 범위 안에 있으면서 아파트가 있다면
					cnt++; //단지내 집의 수 증가
					arr[nx][ny] = 0; //중복으로 검사하지 않기위해 0으로 바꾸고
					q.push(make_pair(nx, ny)); //좌표를 큐에 삽입
				}
			}
		}
	}
	return cnt; //단지내 집의 숫자를 리턴
}

int main()
{
	scanf("%d", &N); //정사각형의 길이

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%1d", &arr[i][j]); 
		}
	}

	vector<int> v; //각 단지내 집의 수를 저장할 곳
	int count = 0; //단지의 수
	for (int x = 0; x < N; x++) {
		for (int y = 0; y < N; y++) {
			if (arr[x][y] == 1) { //만약 해당 좌표에 아파트가 있다면
				count++;//단지의 수를 하나 늘려주고
				v.push_back(BFS(x, y)); //BFS연산
			}
		}
	}
	printf("%d\n", count); //단지의 수
	sort(v.begin(), v.end()); //정렬을 한 후
	for (int i = 0; i < v.size(); i++)
		printf("%d\n", v[i]); //오름차 순으로 출력
}