(백준 2667번 단지번호 붙이기C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 4

크기가 작다고 막 짜다가 디버깅하는데 눙물날 뻔했다..

 

백준 2667번

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

2667번: 단지번호붙이기

 

//2667번 단지번호 붙이기
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Graph {
public:
	int N; 
	int arr[26][26];
	
	int dir_x[4] = { 0, -1, 0, 1 };
	int dir_y[4] = { 1, 0, -1, 0 };
	vector<int> v;
	int cnt = 0;
	Graph(int N) : N(N) {}

	void sorting() {
		stable_sort(v.begin(), v.end());
	}

	bool isInside(int x, int y) {
		if (x < 0 || y < 0 || x >= N || y >= N) return false;
		return true;
	}

	int dfs() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int temp = 0;
				if (arr[i][j] != 0) {
					temp += dfs(i, j);
					cnt++;
					v.push_back(temp);
				}
			}
		}
		return cnt;
	}

private:
	int dfs(int x, int y) {
		//★자꾸 빼먹는 부분!!!!
		arr[x][y] = 0;
		int temp = 1;
		for (int i = 0; i < 4; i++) {
			int x_next = x + dir_x[i];
			int y_next = y + dir_y[i];
			if (isInside(x_next, y_next) && arr[x_next][y_next] == 1) {
				temp += dfs(x_next, y_next);
			}
		}
		return temp;
	}



};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N; cin >> N;
	Graph g(N);

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

	cout << g.dfs()<< "\n";
	g.sorting();
	for (auto x : g.v) {
		cout << x << "\n";
	}
}

주의해야 할 점 : 

입력을 받을 때 띄어쓰기가 없기 때문에 입력이 하나의 string으로 인식된다!

이 부분을 잘 감안해야 하며, 마지막에 답을 sorting하는 과정이 필요하다.