[ 백준 BOJ / c++ ] 2667번 단지번호붙이기

 

🤔 문제

 

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

 

 

---

👀 접근 방식

그래프 탐색 알고리즘을 활용해 탐색하여 집 개수를 구해 출력하였다. 그래프 탐색 알고리즘으로 BFS를 사용하였다. 

1. (값이 1 , 미방문) 조건을 만족하는 배열의 원소에 대하여 bfs 진행
2. 집 개수와 단지 수를 저장
3. 단지내 집 개수를 오름차순 정렬
4. 출력

---

💻 코드

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

using namespace std;


int n;

int clusters = 0;
vector<int> houseCnts;

int maps[27][27];
bool visit[27][27];


void BFS(int y, int x)
{
	int houseCnt = 1;

	queue<pair<int, int>> qqq;
	qqq.push({ y,x });
	visit[y][x] = true;

	while (!qqq.empty()) {

		pair<int, int> front = qqq.front();
		qqq.pop();

		int nx = front.second;
		int ny = front.first;

		// 현재 위치 기준 상하좌우 중 값이 1이고 미방문한 위치를 큐에 추가 및 방문 처리

		if (!visit[ny - 1][nx] && maps[ny - 1][nx] == 1)
		{
			visit[ny - 1][nx] = true;
			qqq.push({ ny - 1,nx });
			houseCnt++;
		}

		if (!visit[ny + 1][nx] && maps[ny + 1][nx] == 1)
		{
			visit[ny + 1][nx] = true;
			qqq.push({ ny + 1,nx });
			houseCnt++;
		}

		if (!visit[ny][nx-1] && maps[ny][nx-1] == 1)
		{
			visit[ny][nx-1] = true;
			qqq.push({ ny,nx -1});
			houseCnt++;
		}

		if (!visit[ny][nx+1] && maps[ny][nx+1] == 1)
		{
			visit[ny][nx+1] = true;
			qqq.push({ ny,nx+1 });
			houseCnt++;
		}

	}


	clusters++;
	houseCnts.push_back(houseCnt);
}

int main()
{ 
	// 지역 크기 입력
	cin >> n;

	// 단지 정보 저장
	for (int i = 1; i <= n; ++i)
	{
		string input;
		cin >> input;

		for (int j = 1; j <= n; ++j)
		{
			maps[i][j] = input[j - 1] - '0';
		}
	}

	// 모든 원소 중 값이 1이고 미방문한 원소에 대해 BFS 진행
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (maps[i][j] == 1 && !visit[i][j])
			{
				BFS(i, j);
			}
		}
	}

	// 단지 수 출력
	cout << clusters << endl;

	// 단지 내 집 개수 정렬
	sort(houseCnts.begin(), houseCnts.end());

	// 단지 내 집 개수 출력
	for (auto& vec : houseCnts)
	{
		cout << vec << '\n';
	}

	return 0;
}