백준 2667 번 - 단지번호붙이기(C++/BFS/Graph)

문제

 

접근법

집단을 이루고있는 개수, 그 집단의 구성수 를 보고 그래프로 풀수 있겠다 생각했다.

다만 탐색 이전에 미리 노드간의 연결을 표현했던것 과는 다르게, bfs를 하면서 상하좌우를 탐색하면서 길을 찾아나가야 했다.

이전 BFS문제들과 탐색방법 하나만 달라서 접근은 쉬웠으나, 

 

입력을 띄어쓰기 없이 받는다.

즉 0 1 0 0 0 1 1

이 아니라

0100011 로 받는다.

string으로 한줄을 받고, 한 문자마다 '0' 을 빼주어서 배열에 넣어주었다.

	for (int i = 0; i < N; i++)
	{
		cin >> num;
		for (int j = 0; j < N; j++)
		{
			arr[i][j] = num[j] - '0';
		}

	}

 

탐색은 dx, dy의 배열을 미리 만들어 주어서 for문을 돌아 탐색 방향을 지정해주고(상하좌우)

범위가 초과나면 continue를 해주었다.

		for (int i = 0; i < 4; i++)
		{
			int nx = here.x + dx[i];
			int ny = here.y + dy[i];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1)
				continue;

			if (arr[ny][nx] && !visited[ny][nx]) {
				coord.push({ nx, ny });
				visited[ny][nx] = 1;
				cnt++;
			}
		}

나머진 일반 bfs와 동일하다

 

코드

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

using namespace std;

int arr[25][25] = { 0, };
int visited[25][25] = { 0, };

struct coords {
	int x;
	int y;
};

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

int bfs(coords c, int N)
{
	queue<coords> coord;
	coord.push(c);
	visited[c.y][c.x] = 1;
	int cnt = 1;
	while (!coord.empty())
	{
		coords here = coord.front();
		coord.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = here.x + dx[i];
			int ny = here.y + dy[i];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1)
				continue;

			if (arr[ny][nx] && !visited[ny][nx]) {
				coord.push({ nx, ny });
				visited[ny][nx] = 1;
				cnt++;
			}
		}


	}
	return cnt;
}

int main()
{
	int N;
	cin >> N;
	string num;
	vector<int> ans;
	for (int i = 0; i < N; i++)
	{
		cin >> num;
		for (int j = 0; j < N; j++)
		{
			arr[i][j] = num[j] - '0';
		}

	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (visited[i][j] == 0 && arr[i][j] != 0)
			{
				coords c;
				c.x = j;
				c.y = i;
				int cnt = bfs(c, N);
				ans.push_back(cnt);
			}
		}
	}
	std::sort(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for (int a : ans)
	{
		cout << a << "\n";
	}

}

코드 간소화의 흔적..