C++) [BOJ] 2667 단지번호붙이기

2667번: 단지번호붙이기 (acmicpc.net)

2667번: 단지번호붙이기

 

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

#define MAX_NODE_SIZE 25
#define Direction 4

namespace AdressNumber 
{
	class DFS 
	{
	private:
		struct Point
		{
			int row;
			int col;
		};
		int sizeNum;
		int arrGraph[MAX_NODE_SIZE][MAX_NODE_SIZE];
		int arrDirection[Direction][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
		vector<int> vecAdress;

		void Input()
		{
			cin >> this->sizeNum;
			memset(this->arrGraph, 0, sizeof(this->arrGraph));

			for (int i = 0; i < this->sizeNum; i++)
			{
				string line;
				cin >> line;

				for (int j = 0; j < this->sizeNum; j++)
				{
					// 아스키코드 값을 사용하여 형 변환
					this->arrGraph[i][j] = line[j] - '0';
				}
			}
		}

		void Solve()
		{
			bool arrVisited[MAX_NODE_SIZE][MAX_NODE_SIZE] = { false };

			for (int i = 0; i < this->sizeNum; i++)
			{
				for (int j = 0; j < this->sizeNum; j++)
				{
					if (this->arrGraph[i][j] && !arrVisited[i][j])
					{
						stack<Point> stackBuffer;
						stackBuffer.push({ i, j });
						arrVisited[i][j] = true;
						int currentAdressCnt = 1;

						while (!stackBuffer.empty())
						{
							Point currentNodePoint = stackBuffer.top();
							stackBuffer.pop();

							for (int k = 0; k < Direction; k++)
							{
								int currentRow = currentNodePoint.row + this->arrDirection[k][0];
								int currentCol = currentNodePoint.col + this->arrDirection[k][1];

								if (currentRow < this->sizeNum && currentRow >= 0 &&
									currentCol < this->sizeNum && currentCol >= 0 &&
									this->arrGraph[currentRow][currentCol] &&
									!arrVisited[currentRow][currentCol])
								{
									stackBuffer.push({ currentRow, currentCol });
									arrVisited[currentRow][currentCol] = true;

									currentAdressCnt++;
								}
							}
						}

						this->vecAdress.push_back(currentAdressCnt);
					}
				}
			}

			sort(this->vecAdress.begin(), this->vecAdress.end());
		}

		void Output()
		{
			cout << this->vecAdress.size() << "\n";
			for (int i = 0; i < this->vecAdress.size(); i++)
			{
				cout << this->vecAdress[i] << "\n";
			}
		}

	public: 
		DFS()
		{
			Input();
			Solve();
			Output();
		}
	};
}

int main() 
{
	AdressNumber::DFS();
}