백준 2667번 단지번호붙이기

2470 단어 백준BFSBFS

문제 링크

설명

BFS를 이용하여 기본적으로 풀었다.
queue에 넣어줄때와, 처음에 각각 count를 이용하여 가구 수를 구하였으며
main문에서 graph에서 1 이지만 아직 방문하지 않은곳이 있다면 houseCnt++ 후 들어가도록 설계했다

소스 코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int dx[] = { -1,1,0,0 };
bool visited[26][26];
int dy[] = { 0,0,1,-1 };
int graph[26][26];
	int cnt = 0;
int k;
int houseCnt = 0;
int houseNum[10000];
void bfs(int start,int now) {
	queue<pair<int, int>> q;
	visited[start][now] = true;
	q.push({ start,now });

	houseNum[houseCnt]++;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (graph[ny][nx] == 0) continue;
			if (nx < 0 || nx >= k || ny < 0 || ny >= k) continue;

			if (!visited[ny][nx]) {
				q.push({ ny,nx });
				visited[ny][nx] = true;
				houseNum[houseCnt]++;
			}
		}


	}

	
}
int main()
{

	cin >> k;
	for (int y = 0; y < k; y++) {
		for (int x = 0; x < k; x++) {
			scanf("%1d", &graph[y][x]);
		}
	}
	
	for (int y = 0; y < k; y++) {
		for (int x = 0; x < k; x++) {
			if (visited[y][x] == false && graph[y][x] == 1) {
				houseCnt++;
				bfs(y,x);

			}
	
		}
	}


	cout << houseCnt << endl;
	sort(houseNum + 1, houseNum + houseCnt+1);

	for (int i = 1; i <= houseCnt; i++) {
		cout << houseNum[i] << endl;
	}

	return 0;
}

좋은 웹페이지 즐겨찾기