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

📌 문제

BOJ 바로가기

그래프 탐색 문제이다. 한 집이 존재하고 그 집의 상하좌우에 또 다른 집이 존재할 경우 집과 집 사이에 간선이 존재한다고 판단할 수 있다. BFS 또는 DFS를 통해 문제를 해결할 수 있다.

🗡 풀이

지도의 정보를 담은 map 배열, 방문했는지 판단하기 위한 visited 배열, 그리고 답을 출력하기 위한 ans 벡터를 선언했다. for문을 사용해 지도를 탐색하는데, 해당 위치를 방문하지 않았다면 bfs함수를 호출해서 visited값을 true로 바꿔주고 집의 개수를 카운트한다. 마지막에 큐가 비면서 그래프 탐색이 끝나면 ans백터에 cnt값을 push해준다.

dx와 dy배열은 코드를 간단하고 효율적으로 짜기 위해 선언된 배열이다. x, y값에 미리 초기화해둔 dx[i], dy[i]를 더해주면 if문을 네 번 쓰는 대신 for문을 한 번 쓰는 것만으로도 (x, y)의 상하좌우를 탐색할 수 있다.

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

int n;
int map[26][26];
vector<int> ans;
bool visited[26][26] = { false };
// 상, 하, 좌, 우로 가기 위한 배열
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void bfs(int row, int col)
{
	queue<pair<int, int>> q;
	q.push(make_pair(row, col));
	visited[row][col] = true;
	int cnt = 0;
	cnt++;
	while (!q.empty())
	{
		int front_x = q.front().first;
		int front_y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			// next_x, next_y는 다음으로 push할 인덱스 후보
			int next_x = front_x + dx[i];
			int next_y = front_y + dy[i];
			if (0 <= next_x && next_x < n && 0 <= next_y && next_y < n // 범위는 지도를 넘어가면 안됨
				&& visited[next_x][next_y] == false && map[next_x][next_y] == 1)
			{
				q.push(make_pair(next_x, next_y));
				visited[next_x][next_y] = true;
				cnt++;
			}
		}
	}
	ans.push_back(cnt);
}

int main()
{
	cout.tie(nullptr);
	cin >> n;
	// 지도 입력받기
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%1d", &map[i][j]);
		}
	}
	// 지도 탐색
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (visited[i][j] == false && map[i][j] == 1)
			{
				bfs(i, j);
			}
		}
	}
	// 결과 도출
	sort(ans.begin(), ans.end());
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << '\n';
}