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

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

2667번: 단지번호붙이기

안녕하세요. 현's story 입니다.

 

이번 시간에는 단지번호붙이기 풀이법에 대해 설명해드리겠습니다.

 

이 문제의 경우 여러가지 변형된 문제를 다수 풀어본 경험이 있습니다.

자신감(?)에 넘쳐서 바로 풀었더니!!!땅 하고 프로그램이 안돌아가더라고요..

 

 

다시 주의깊게 보니까 입력이 변수 간에 서로 띄워져있지 않고

모두 붙여져 있는 형태로 입력이 들어오기 때문에 

 

한자리만 입력받을 필요가 생겼습니다.

 

int로 입력 받으면 더 빨리 진행할 수 있는데, 붙여져있는 형태로 입력을 받기 때문에 

string으로 입력을 받고 일일히 다 띄워주는 역할을 진행했습니다. (사실 scanf로 %1d로 받을 수 있지만 풀 때 생각이 나지 않았네요 ㅠㅠ)

 

 

입력값의 정보는 0, 1이 있는데, 1인 지역은 집을 의미하는 겁니다. 그래서

 

NxN만큼 for문을 돌면서 '1'값을 찾게 되면 BFS탐색을 통해 count를 했습니다. 그 count값을 deque에 삽입하여 모든 연산이 끝나고 나서 오름차순으로 정렬한 뒤, 출력하도록 만들었습니다.

 

출력 첫 째줄에 총 집의 개수를 출력하고 하는데, NxN만큼 for문을 돌면서 '1'을 만나면  count을 1 추가 해주시며 됩니다.

 

주의 할 점은!!!! 내가 방문했고, count를 했던 좌표는 '2'로 만들어주어야 합니다. '2'는 방문했다는 의미로,

무한루프를 방지해주고, 또한, 들렸던 집의 갯수를 또 카운트하는 일이 발생하지 않도록 합니다.

 

전체 코드는 다음과 같습니다.

 

#include <iostream>
#include <deque>
#include <queue>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>

using namespace std;

#define input_max 25 + 1
#define dir 4

int n;
char map[input_max][input_max];
int dx[] = { -1, 1, 0, 0};
int dy[] = { 0, 0, -1, 1 };

deque<int> dq;

int house;
int bfs(int x, int y) {  // BFS 탐색

	queue<pair<int, int>> q;

	int cnt = 1;
	map[x][y] = '2';

	q.push(make_pair(x, y));

	while (!q.empty()) {

		int x = q.front().first;
		int y = q.front().second;

		q.pop();

		for (int k = 0; k < dir; k++) {

			int nx = x + dx[k];
			int ny = y + dy[k];

			if (nx >= 0 && nx < n && ny >= 0 && ny < n && map[nx][ny] == '1') {  // 방문하지 않은 곳 '1'만 찾음

				q.push(make_pair(nx, ny));
				map[nx][ny] = '2';  // 방문했기 때문에 '2'로 변환
				cnt++;
			}
		}
		
	}

	return cnt;  // 집의 넓이 총 개수를 반환시켜줌

	
}

void solution() {


	cin >> n;

	for (int i = 0; i < n; i++) {
		
		string str;
		cin >> str;
	
		strcpy(map[i], str.c_str());  // 문제 출제자는 띄워쓰기를 꼭 해주어서 다시 문제 내주시기를

	}

			


	

	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) {

			if (map[i][j] == '1') {  // 1을 발견하면 BFS탐색을 합니다. 그리고 집을 찾았다는 의미로 house++을 합니다.
				house++;
				int cnt = bfs(i, j);

				dq.push_back(cnt);

			}
		}
	
	


	sort(dq.begin(), dq.end());  // 오름차순으로 정렬

	cout << house << '\n';  // house의 총 개수를 먼저 출력하고

	while (!dq.empty()) {
	
		
		cout << dq.front() << '\n';  // 오름 차순으로 정렬된 값들을 하나씩 출력

		dq.pop_front();

	}

}


int main() {


	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solution();

	return 0;
}