[2667번] 단지번호붙이기

- DFS

//인접행렬이나 인접리스트를 만들지 않아도
//2차원 배열상에서는 한정점과 연결된 간선을 위,왼쪽,오른쪽, 아래만 탐색하면 됌.
//DFS나 BFS 알고리즘을 이용해서 어떻게 이어져있는지 확인할 수 있다.
//d[i][j] = (i,j)를 방문안했으면 0, 했으면 단지 번호, 마지막에는 단지번호의 갯수를 구하면됌.
//집이 있는데 아직 방문하지 않았으면은 집의 개수를 늘려주고 탐색을 시작.
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

const int MAX = 30;
int map[MAX][MAX];
int check[MAX][MAX]; //0(방문하지않음), 1~(단지번호)
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int n;
int ans[30*30];

void dfs(int x, int y, int cnt)
{
	check[x][y] = cnt;
	//상,하,좌,우
	for(int k = 0; k < 4; k++)
	{
		int nx = x + dx[k];
		int ny = y + dy[k];
		//0~n-1까지의 범위 체크
		if(nx >= 0 && nx < n && ny >= 0 && ny < n)
		{
			if(map[nx][ny] == 1 && check[nx][ny] == 0)
			{
				printf("(%d,%d)\n", nx, ny);
				dfs(nx, ny, cnt);
			}
		}
	}
}

int main()
{
	scanf("%d", &n);

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			scanf("%1d", &map[i][j]);
		}
	}

	int danji_cnt = 0;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(map[i][j] == 1 && check[i][j] == 0) //집이 있는 곳이거나 방문하지 않은 경우.
			{
				dfs(i, j, ++danji_cnt);
			}
		}
	}

	printf("%d\n", danji_cnt); //총단지수
    //각 단지내 집의 수를 오름차순으로 정렬하여 한줄에 출력
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			ans[check[i][j]] += 1; 
		}
	}

	sort(ans+1, ans+danji_cnt+1);
	for(int i = 1; i <= danji_cnt; i++)
	{
		printf("%d\n", ans[i]);
	}

	return 0;
}

- BFS

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

const int MAX = 30;
int map[MAX][MAX];
int check[MAX][MAX];
int n;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int ans[MAX*MAX];

void bfs(int x, int y, int cnt)
{
	queue<pair<int, int>> Queue;
	Queue.push(make_pair(x,y));
	check[x][y] = cnt;

	while(!Queue.empty())
	{
		x = Queue.front().first;
		y = Queue.front().second;
		Queue.pop();
		//상,하,좌,우
		for(int k = 0; k < 4; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];
			if(nx >= 0 && nx < n && ny >= 0 && ny < n)
			{
				if(map[nx][ny] == 1 && check[nx][ny] == 0)
				{
					check[nx][ny] = cnt;
					Queue.push(make_pair(nx, ny));
				}
			}

		}
	}
}

int main()
{
	scanf("%d", &n);

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			scanf("%1d", &map[i][j]);
		}
	}

	int danji_cnt = 0;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(map[i][j] == 1 && check[i][j] == 0)
			{
				bfs(i, j, ++danji_cnt);
			}
		}
	}

	printf("%d\n", danji_cnt);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			ans[check[i][j]] += 1;
		}
	}

	sort(ans+1, ans+danji_cnt+1);

	for(int i = 1; i <= danji_cnt; i++)
	{
		printf("%d\n", ans[i]);
	}

	return 0;
}