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

문제 해석

0과1로 되어있는 이차원 배열이 주어져있을 때 1이 뭉쳐있는 곳이 몇 개가 있는지 그 각각의 뭉쳐있는 곳에는 1이 몇개가 있는지 츌력하는 문제이다.

발상

자료구조 수업시간에 배웠던 그래프 구조랑 비슷한 것 같아 범위 기반 탐색을 통해 단지가 몇 개인지 각각의 단지의 몇개가 있는지를 확인하면 편할 것 같다고 생각하였다.

이중포문을 통해 1이면서 방문하지 않은 곳에서 범위 기반 탐색을 시작해서 탐색을 하면 탐색한 개수가 단지의 개수이고, 그 탐색을 하면서 재귀적으로 함수가 실행될 때 마다 숫자를 세 주어서 몇 개의 1이 있는지 확인해준다.

탐색이 끝날때 마다 단지 안의 1의 개수를 벡터에 넣어주고, 벡터의 사이즈를 출력하게 되면 단지의 개수, 벡터를 오름차순으로 정렬하고 출력을 해주게 되면 1의개수를 출력해줄 수 있게 된다.

코드

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

int px[4]{ 1,-1,0,0 };
int py[4]{ 0,0,-1,1 };

int map[26][26] = {};
bool visited[26][26] = {};

int n;

int result = 0;

void bfs(int x,int y){
	result++;
	visited[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int curX = x + px[i];
		int curY = y + py[i];

		if (curX >= n || curY >= n || curX < 0 || curY < 0) continue;

		if (visited[curX][curY] == false && map[curX][curY] == 1) {
			bfs(curX, curY);
		}
	}
}

int main(void) {
	vector<int> complexVec;
	string tmp;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> tmp;

		for (int j = 0; j < tmp.size(); j++) {
			map[i][j] = (int)tmp[j] - '0';
		}
	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && visited[i][j] == false) {
				bfs(i, j);
				complexVec.push_back(result);
				result = 0;
			}
		}
	}

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

	cout << complexVec.size() << '\n';
	for (int i = 0; i < complexVec.size(); i++) 
		cout << complexVec[i] << '\n';
	return 0;
}

느낀점

수업시간에 그래프 탐색을 배웠을 때 굉장히 어지럽고 어려워서 힘들었는데 이러한 문제를 직접 풀어보면서 그래프 탐색이 어느 정도 쉬워진 단계까지 올라온 것 같아 뿌듯하다