백준 2667

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

이러한 문제류는 이제 dfs든 bfs로 풀기 쉬워졌다 이문제의 경우 자신을 기준으로 상하좌우로만 이동 할 수있기때문에 깊이우선 탐색으로 풀어 보았다 이문제는 어차피 단지의 개수를 세야 하기때문에 모든점을 한번에 다방문하면서 개수를 셀수 있는 dfs를 사용하였다. 이문제의 핵심 부분은

	if ((!visited[i][j + 1]) && map[i][j+1]==1)
		dfs(i, j + 1);
	if ((!visited[i][j - 1]) && map[i][j - 1]==1)
		dfs(i, j - 1);
	if ((!visited[i - 1][j]) && map[i-1][j]==1)
		dfs(i - 1, j);
	if ((!visited[i + 1][j]) && map[i + 1][j]==1)
		dfs(i + 1, j);

이부분이다 나를 기준으로 내 상하좌우중 방문한적이 없는 애들이 없으면 방문한다 그후 이함수 부분을 재귀적으로 호출하기 때문에 내 다음애들이 없으면 다시 부모로 돌아가서 다음거를 탐색한다 즉 재귀함수로 dfs를 구현한것이다

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int map[26][26];
bool visited[26][26];
int countnum = 0;
int danjicount = 0;
vector<int> answer;
void dfs(int i, int j) {
	countnum++;
	visited[i][j] = true;
	if ((!visited[i][j + 1]) && map[i][j+1]==1)
		dfs(i, j + 1);
	if ((!visited[i][j - 1]) && map[i][j - 1]==1)
		dfs(i, j - 1);
	if ((!visited[i - 1][j]) && map[i-1][j]==1)
		dfs(i - 1, j);
	if ((!visited[i + 1][j]) && map[i + 1][j]==1)
		dfs(i + 1, j);
}
int main() {
	int N;
	string temp;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> temp;
		for (int j = 0; j <N; j++) {
			map[i][j + 1] = temp[j]-'0';
		}
	} 

	for (int i = 1; i <= N; i++) {	
		for (int j = 1; j <= N; j++) {
			countnum = 0;
			if (visited[i][j] || map[i][j]==0)
				continue;
			dfs(i, j);
			danjicount++;
			if(countnum)
				answer.push_back(countnum);
		}
	}
	
	sort(answer.begin(), answer.end());
	cout << danjicount << '\n';
	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << '\n';
	}

}