백준 단지번호붙이기(2667)

1을 만났을 때, 상하좌우에 인접한 다른 1이 있는지를 계속 검사한다. 내가 원하는 선택지로부터 계속해서 파고들기때문에, 이는 dfs알고리즘을 활용하여 푸는것이 적절하다고 생각하였다.

visited배열이 필요한 이유 : 한번 이동한 경로를 체크해야 다음 번 반복문에서 같은 노드를 중첩하여 검사하지 않기 때문이다.

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

int map[25][25] = { 0, };
int visited[25][25] = { 0, };
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int cnt = 0;

void dfs(int x, int y,int size)
{
	if (map[y][x] == 1)
	{
		cnt++;
		visited[y][x] = 1;
		for (int i = 0; i < 4; i++)
		{
			if (x + dir[i][0] >= size || y + dir[i][1] >= size ||
				x + dir[i][0] < 0 || y + dir[i][1] < 0)
				continue;
			if (visited[y + dir[i][1]][x + dir[i][0]] == 1)
				continue;
			if (map[y + dir[i][1]][x + dir[i][0]] == 0)
				continue;
			visited[y + dir[i][1]][x + dir[i][0]] = 1;
			dfs(x + dir[i][0], y + dir[i][1], size);
		}
		return;
	}
	return;
}
int main()
{
	int size;

	vector<int> cnts;
	scanf("%d", &size);
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
			scanf("%1d", &map[i][j]);
	}
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			cnt = 0;
			if (map[i][j] == 1 && visited[i][j] == 0)
			{
				visited[i][j] = 1;
				dfs(j, i, size);
				cnts.push_back(cnt);
				cnt = 0;
			}
		}
	}
	sort(cnts.begin(), cnts.end(), less<int>());
	printf("%d\n",cnts.size());
	for (int i = 0; i < cnts.size(); i++)
	{
		printf("%d\n", cnts[i]);
	}
}