[BAEKJOON] 2667번 : 단지 번호 붙이기

문 제

 

소 스  코 드

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>


constexpr int MAXSIZE{ 25 };

char map[MAXSIZE][MAXSIZE]{ {0, }, };


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

	int N;
	std::cin >> N;

	for (int i = 0; i < N; ++i) std::cin >> map[i];


	std::vector<int> logs;
	int logIndex	{ 0 };
	logs.reserve(MAXSIZE * MAXSIZE);

	// BFS ( for문은 최대 25 * 25 625번 실행 )
	// 
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if ('0' == map[i][j]) continue;

			std::stack<std::pair<int, int>> nearby;
			map[i][j] = '0';
			nearby.push(std::make_pair(i, j));
			logs.emplace_back(1);

			while (!nearby.empty()){
				int x = nearby.top().first;
				int y = nearby.top().second;
				nearby.pop();

				// left
				if ((y > 0) && ('0' != map[x][y - 1])) {
					map[x][y - 1] = '0';
					nearby.push(std::make_pair(x, y - 1));
					++logs[logIndex];
				}
				// right
				if ( (y < N - 1) && ( '0' != map[x][y + 1])) {
					map[x][y + 1] = '0';
					nearby.push(std::make_pair(x, y + 1));
					++logs[logIndex];
				}
				// up
				if ( (x < N - 1 )&& ('0' != map[x + 1][y])) {
					map[x + 1][y] = '0';
					nearby.push(std::make_pair(x + 1, y));
					++logs[logIndex];
				}
				// down
				if ( (x > 0 ) && ('0' != map[x - 1][y])) {
					map[x - 1][y] = '0';
					nearby.push(std::make_pair(x - 1, y));
					++logs[logIndex];
				}
			}
			++logIndex;

		}
	}

	std::sort(logs.begin(), logs.end());

	std::cout << logs.size() << '\n';
	for (const int& a : logs) std::cout << a << '\n';

	

	return 0;
}

 

풀 이

 

• BFS( 너비 기반 탐색 ) 을 통하여 구현 하였습니다.
• 입력을 받을시 char배열을 통하여 입력을 받았습니다.

입력을 받을 때, 0110100과 같이 띄어쓰기가 없이 입력이 되기 때문에 char 배열이나, string을 통하여 입력을 받을 수 있는데 char 배열을 통하여 입력을 받았습니다.

BFS와 DFS의 2가지 방법의 탐색이 있지만, 저는 DFS 깊이를 기반으로 하는 탐색을 이용하여 구현 하였습니다.

stack을 통하여 점차 확장해 나가는 형식을 사용하였고, 4방향의 검사를 통하여 점차 단지를 확인 하였습니다.

 

vector를 통하여 단지 내에 건물 갯수를 저장하였는데, vector의 멤버함수 size()를 통하여 단지의 갯수를 알 수 있고, algorithm 안에 sort 함수를 통하여 간단히 오름차순으로 정렬 하였습니다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : www.acmicpc.net/problem/2667

2667번: 단지번호붙이기