[BOJ] C++ 2667 "단지번호 붙이기" 문제 풀이 _ nov

#INFO

난이도 : SILVER1

문제 유형 : BFS

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

2667번: 단지번호붙이기

---

#SOLVE

연결된 영역(단지)의 개수와 각 영역(단지)의 넓이를 오름차 순으로 출력하면 되는 간단한 BFS 문제이다. 

string board[27] : 단지의 정보를 저장할 배열 0 : 집이 없는곳 1 : 집이 있는 곳

bool isVisited[27] : 단지의 방문 여부를 저장할 배열

int dx[4] , int dy[4] : 상하좌우 이동을 도와줄 변수

 

크기 n 배열의 정보를 입력받는다.

	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> board[i];
	}

 

count 변수에는 연결된 영역(단지)의 개수를 area 벡터에는 영역의 넓이를 저장한다.

	int count = 0;
	vector<int> area;

 

만약 board[i][j]가 '1' 즉, 집이 있는 곳 이고 !isVisited[i][j] 방문하지 않은 집일 경우 BFS 탐색을 시작한다. 

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(board[i][j] == '1' && !isVisited[i][j]) {
				queue<pair<int,int>> Q;
				count++;
				Q.push({i, j});
				isVisited[i][j] = 1;
				int width = 1;
				while(!Q.empty()) {
					auto cur = Q.front(); 
					Q.pop();
					for(int dir = 0; dir < 4; dir++) {
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir];
						if(nx < 0 || nx >= n || ny < 0 || ny >= n) 
							continue;
						if(board[nx][ny] == '0' || isVisited[nx][ny] == 1) 
							continue;
						Q.push({nx,ny});
						isVisited[nx][ny] = 1;
						width++;
					}
				}
				area.push_back(width);
			}
		}
	}

 

count (단지의 개수) 를 출력하고, sort 함수를 이용해 area 벡터를 오름차 순으로 정렬한 뒤 벡터의 모든 원소를 출력한다.

	cout << count << '\n';
	sort(area.begin(), area.end());
	for (int i : area) {
		cout << i << '\n';
	}

---

#CODE

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[27];
bool isVisited[27][27];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> board[i];
	}
	
	int count = 0;
	vector<int> area;

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(board[i][j] == '1' && !isVisited[i][j]) {
				queue<pair<int,int>> Q;
				count++;
				Q.push({i, j});
				isVisited[i][j] = 1;
				int width = 1;
				while(!Q.empty()) {
					auto cur = Q.front(); 
					Q.pop();
					for(int dir = 0; dir < 4; dir++) {
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir];
						if(nx < 0 || nx >= n || ny < 0 || ny >= n) 
							continue;
						if(board[nx][ny] == '0' || isVisited[nx][ny] == 1) 
							continue;
						Q.push({nx,ny});
						isVisited[nx][ny] = 1;
						width++;
					}
				}
				area.push_back(width);
			}
		}
	}
	
	cout << count << '\n';
	sort(area.begin(), area.end());
	for (int i : area) {
		cout << i << '\n';
	}
	return 0;
}