백준 2667 - 단지번호붙이기

문제 링크입니다 https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

기본적인 BFS,DFS문제입니다. 저는 BFS로 풀었습니다.

1이 집이 있는곳, 0이 집이 없는 곳을 뜻합니다.

1이 연속적으로 모여있을때 한개의 단지임을 나타냅니다. 위의 그림을 보면 3개의 단지가 있는 것을 볼 수 있습니다. 

문제를 풀때 접근방법은 이중 for문을 통해서 첫번째 1를 찾습니다.  그후에 1의 좌표를 입력받은 뒤에 그 좌표에서부터 BFS를 시작합니다.(좌표를 큐에 넣어줍니다.) BFS가 끝났을 경우 단지의 갯수를 하나 증가합니다. 

BFS를 도는 횟수를 변수를 통해 입력받은 뒤에 vector에 넣어줍니다. 모든 BFS가 끝난뒤에 vector를 sort를 통해서 오차순 정렬을 해준뒤에 단지의 갯수와 단지속 집의 갯수를 출력합니다.

scanf("%1d", &)를 사용한다면 문자열을 사용하지 않더라도 띄어쓰기 없이 입력받을 수 있습니다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;

int house[26][26];
int check[26][26];
int arr[4] = { 0,1,0,-1 };
int arr2[4] = { 1,0,-1,0 };
int number;
int number_house;
typedef struct qu {
	int x;
	int y;
}qu;
queue<qu> q;
vector<int> v;

void bfs(int x, int y) {
	check[x][y] = 1;
	int cnt = 0;
	q.push({ x,y });
	while (!q.empty()) {
		int x1 = q.front().x;
		int y1 = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x1 + arr[i];
			int yy = y1 + arr2[i];
			if (xx >= 1 && xx <= number && yy >= 1 && yy <= number) {
				if(check[xx][yy] == 0 && house[xx][yy] == 1){
					check[xx][yy] = 1;
					q.push({ xx,yy });
				}
			}
		}
		cnt++;
	}
	v.push_back(cnt);
	number_house++;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> number;
	for (int i = 1; i <= number; i++) {
		for (int j = 1; j <= number; j++) {
			scanf("%1d", &house[i][j]);
		}
	}
	for (int i = 1; i <= number; i++) {
		for (int j = 1; j <= number; j++) {
			if (house[i][j] == 1 && check[i][j] == 0) {
				bfs(i, j);
			}
		}
	}
	sort(v.begin(), v.end());
	cout << number_house << "\n";
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << "\n";
	}
	return 0;
}

질문있으시면 댓글 남겨주세요!