[boj][c++] 2667 단지번호붙이기

2667 단지번호붙이기

bfs/dfs를 꾸준히 안 풀면 감을 잃을 것 같아서 풀어봤다. 자만하다가 결국 내 힘만으로 풀지 못해서 이전에 다른 bfs문제를 풀었던 방식을 참고했다. ㅜㅜ

• 그림 1의 그래프를 탐색하기 위해서 main에서 이중반복을 돌린다.
• main의 이중반복에 조건 충족하는 노드(방문하지 않았고 값이 1인 노드)를 bfs함수에 넣는다.
• 값이 1인 인접노드들을 모두 방문처리하며 현재 단지 배열에 값을 더한다.
• main에서의 이중반복이 종료되면 단지 수와 각 단지의 집 수를 단지 배열에서 확인할 수 있다.

그래프의 인접노드를 확인하기 위해서 xs와 xy배열을 만들었다. bfs 내에서 총 4번 반복하며 좌우상하 노드를 탐색하게 된다. bfs의 구성은 간단했는데 main에서 이중반복을 돌리지 않고 bfs(graph[1][1])만 작성해서 계속 헤맸다. 코드 작성하면서도 이런 코드라면 한 단지의 수밖에 알수없고 그마저도 첫 노드의 값이 0이면 아무 동작하지 않을거라고 생각했는데 내 생각이 맞았다. dfs와 개념을 혼동했고 그마저도 제대로 된 코드가 아니었기에 문제에 맞춰진 공부를 했다는 생각이 들었다.

내일은 클러스터 나가서 처음으로 본과정 과제 도전하려고 한다. 풀기 전에 bfs/dfs한문제 풀어야겠다.

#include	<iostream>
#include	<deque>
#include	<algorithm>
using namespace std;

int graph[26][26];
bool visit[26][26];
int n;
int now = 0;
int dong[25 * 25 + 1];
int xs[4] = { 0,0,1,-1 };
int ys[4] = { 1,-1,0,0 };

void bfs(int x, int y)
{
	deque<pair<int, int>>q;
	q.push_back({ x,y });
	visit[x][y] = true;
	dong[now]++;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop_front();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + xs[i];
			int ny = y + ys[i];
			if (nx > 0 && nx <= n && ny > 0 && ny <= n)
			{
				if (visit[nx][ny] == false && graph[nx][ny] == 1)
				{
					visit[nx][ny] = true;
					dong[now]++;
					q.push_back({nx, ny});
				}
			}
		}
    }
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < n; j++)
		{
			graph[i][j + 1] = s[j] - '0';
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (visit[i + 1][j + 1] == false && graph[i + 1][j + 1] == 1)
			{
				now++;
				bfs(i + 1, j + 1);
			}
		}
	}
	sort(dong + 1, dong + now + 1);
	cout << now << '\n';
	for (int i = 1; i <= now; i++)
	{
		cout << dong[i] << '\n';
	}
}