C++ [Algorithm] - 백준 2667 단지번호붙이기

문제

---

입출력

---

문제 요약

이 문제는 dfs가 몇번 돌아가는지, dfs 1번 돌아갈 때 몇번 탐색하는지를 구현하는 문제이다.

dfs 개념과 dfs의 재귀함수 과정을 안다면 쉽게 풀 수 있다. 

---

코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int map[25][25];
bool visited[25][25];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int N, house = 1;
vector<int> seq;

void dfs(int x, int y) {
	visited[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < N && ny < N && nx >= 0 && ny >= 0) {
			if (map[nx][ny] == 1 && !visited[nx][ny]) {
				dfs(nx, ny);
				house++;
			}
		}
	}
}


int main() {
	int count = 0;
	string str;
	cin >> N;

	memset(map, 0, sizeof(map));
	memset(visited, false, sizeof(visited));


	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int j = 0; j < N; j++) {
			char a = str[j];
			map[i][j] = a - '0';
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1 && !visited[i][j]) {
				dfs(i, j);
				count++;
				seq.push_back(house);
				house = 1;
			}
		}
	}

	sort(seq.begin(), seq.end());

	cout << count << endl;

	for (int i = 0; i < seq.size(); i++) {
		cout << seq[i] << endl;
	}
}