백준 2667 : 단지번호붙이기

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

★★★☆☆

1. 접근

• 한 집마다 인접한 집을 모두 체크해야 하므로 BFS가 적절하다
• bfs 내부에서, 상하좌우의 집과의 연결성을 확인해주어야 한다
• deque에는 집의 좌표값을 pair로 입력한다
• 배열의 인덱스 값을 넘어서 상하좌우를 비교하게 될 수 있으므로, MAX 값을 2씩 늘려서 받았다.
  (원래는 조건식을 다르게 하는게 맞다)
• 입력값을 한번에 붙여서 주기 때문에, 분리해서 입력받기 위해 char 배열을 사용했다
• 결괏값은 오름차순으로 주어야 하므로 sort 알고리즘을 사용했다

2. 나의 풀이

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
#define MAX 27 // 원래는 25이지만 상하좌우 값 비교를 위해 2씩 늘려줌
using namespace std;

int n,tem;
bool visited[MAX][MAX];
bool graph[MAX][MAX];
deque<pair<int, int>> q;

void bfs(int i,int j) { //너비 우선 탐색
	q.push_back(make_pair(i, j)); //deque에 pair 값 만들어서 넣어주기
	visited[i][j] = true;

	while (!q.empty()) {
		i = q.front().first; //pair값에서 꺼내기
		j = q.front().second;
		//cout << "(" << i << ", " << j << ") 방문\n";
		q.pop_front();

		if (graph[i + 1][j] && !visited[i + 1][j]) { //우
			visited[i + 1][j] = true;
			q.push_back(make_pair(i + 1, j));
		}
		if (graph[i - 1][j] && !visited[i - 1][j]) { //좌
			visited[i - 1][j] = true;
			q.push_back(make_pair(i - 1, j));
		}
		if (graph[i][j + 1]  && !visited[i][j + 1]) { //하
			visited[i][j + 1] = true;
			q.push_back(make_pair(i, j + 1));
		}
		if(graph[i][j -1] &&!visited[i][j - 1]) { //상
			visited[i][j -1] = true;
			q.push_back(make_pair(i, j -1));
		}
		tem++; //단지 가구 수 카운트
	}
	return;
}

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		char input[MAX]; //입력을 위한 char 배열
		cin >> input;
		for (int j = 1; j <= n; j++) {
			if(input[j-1]=='0') graph[i][j]=0; 
			else graph[i][j] = 1;
		}
	}

	vector<int> ret;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (graph[i][j]&& !visited[i][j]) {
				bfs(i, j); 
				ret.push_back(tem); //가구 수 더해주기
				tem = 0;
				//cout << ret.size() << " 끝 =================== \n\n";
			}
		}
	}

	sort(ret.begin(), ret.end()); //오름차순 정렬
	cout << ret.size() << "\n"; // 배열의 크기가 단지의 수
	for (int i = 0; i < ret.size(); i++) {
		cout << ret[i] << "\n";
	}

	return 0;

}