백준 2667 : 단지 번호 붙이기

1. 문제 : https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

2. 문제 접근

• 2차원 배열이 주어지고 이를 조건에 따라 탐색. -> DFS나 BFS를 사용하여 그래프를 탐색

 

3. 문제 해결

1. 주어진 단지 정보를 순차적으로 탐색.
2. $(i, j)$ 노드가 아파트가 존재한다면 BFS나 DFS 탐색 시작.
3. $(i, j)$ 노드가 이미 방문한 노드라면 탐색하지 않음.
4. 노드의 갯수를 차례대로 저장하여 마지막에 정렬 후 반환.

 

4. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> solution(int N, vector<string>& map)
{
	vector<int> answer;
	vector<vector<bool>> visited;

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

	// Initialize the matrix for checking whether the node is visited
	for (int i = 0; i < N; i++)
	{
		vector<bool> temp;

		for (int j = 0; j < N; j++)
		{
			temp.push_back(false);
		}

		visited.push_back(temp);
	}

	// Find connected apartments and add the number of apartments
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			// There is no apartment
			if (map[i][j] == '0') continue;
			// Already visited
			if (visited[i][j]) continue;

			queue<pair<int, int>> bfs;
			
			// Calculate the number of connected apartments
			bfs.push({ i, j });
			visited[i][j] = true;
			int count = 0;

			while (!bfs.empty())
			{
				pair<int, int> pos = bfs.front();
				bfs.pop();
				count++;
				
				int x = pos.first, y = pos.second;
				for (int d = 0; d < 4; d++)
				{
					int tx = x + dx[d], ty = y + dy[d];

					// Out of range, there is no apartment, already visited
					if (tx < 0 || ty < 0 || tx >= N || ty >= N || map[tx][ty] == '0' || visited[tx][ty]) continue;

					visited[tx][ty] = true;
					bfs.push({ tx, ty });
				}
			}

			answer.push_back(count);
		}
	}

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

	return answer;
}

int main()
{
	int N;
	vector<string> map;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		string temp;

		cin >> temp;

		map.push_back(temp);
	}
	
	vector<int> result = solution(N, map);

	cout << result.size() << endl;
	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << endl;
	}

	return 0;
}