#2667 단지번호붙이기

# 문제

# 입력 및 출력

# 풀이

1) BFS (너비 우선 탐색)

#include <iostream>
#include <queue>
#pragma warning (disable:4996)

using namespace std;
int map[27][27]; // 문제에서 주어지는 지도
int visit[27][27]; // 방문했는지 확인하는 배열
int dx[4] = { -1,1,0,0 }; // x 상하좌우 확인용
int dy[4] = { 0,0,-1,1 }; // y 상하좌우 확인용
queue<pair<int, int>> q; // bfs용 큐
priority_queue<int, vector<int>, greater<int>> count_home; // 각 단지내 집의 수 오름차순 정렬용
int N, x, y, bunji = 0, home = 1;

void find() { // 다음 번지를 찾는 함수
	int stop = 0; // for문 break용 변수
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] && !visit[i][j]) { // 지도 상에 길이 있고 방문하지 않은 집
				x = i, y = j;
				stop = 1;
				break;
			}
			else {
				x = -1, y = -1; // 더이상 방문할 곳이 없는 경우엔 x=-1, y=-1이 됨
			}
		}
		if (stop) break; // 이중 for문 동시에 종료 위해 작성
	}
	return;
}

void check() { // 같은 번지 내에 몇개의 집이 있는지 찾는 함수
	while (!q.empty()) { // bfs
		int nx, ny;
		x = q.front().first;
		y = q.front().second; // 큐에서 가져옴
		q.pop(); // 큐에서 삭제
		for (int i = 0; i < 4; i++) {
			nx = x + dx[i]; // 현재 집의 상하좌우 확인용 변수 nx
			ny = y + dy[i]; // 현재 집의 상하좌우 확인용 변수 ny
			if (map[nx][ny] && !visit[nx][ny]) { // 길이 있고 방문하지 않은 집
				visit[nx][ny] = 1; // 방문했다고 표시
				q.push(make_pair(nx, ny)); // 큐에 넣기
				home++; // 번지 내 집의 개수 + 1
			}
		}
		if (q.empty()) bunji++; // 한 번지를 다 돌았으면 번지수 count 변수 + 1
	}
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%1d", &map[i][j]);
		}
	} // 주어진 지도 받아오기
	while (1) {
		find(); // 조회할 번지 찾기
		if (x == -1 && y == -1) break; // 더이상 볼 번지가 없다면 종료
		q.push(make_pair(x, y)); // 조회할 번지가 있다면 처음 집을 큐에 넣기
		visit[x][y] = 1; // 방문했다고 하기
		home = 1; // 같은 번지 내 집 개수 count 변수는 현재 1(처음 집)
		check(); // 같은 번지 내 집 개수 확인
		count_home.push(home); // 집 개수 저장용 큐에 현재 번지의 집 개수 push
	}
	cout << bunji << "\n";
	while (!count_home.empty()) {
		cout << count_home.top() << "\n";
		count_home.pop();
	} // 출력
}

저번에 풀었던 bfs를 응용해서 풀었다

처음에 제출할 때 문제를 잘못 읽어서 출력이 오름차순으로 돼야하는지 몰랐다ㅋㅋ

그래서 틀렸다고 나와서 무슨 문젠가 싶었는데 오름차순 정렬로 출력하래서 우선순위 큐를 사용했다

벡터를 쓰려다가 vector, algorithm 헤더를 선언하기 싫어서 그냥 우선순위 큐를 사용했다

 

 

 

2) DFS (깊이 우선 탐색)

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning (disable:4996)
using namespace std;

int map[27][27];
int visit[27][27];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int N, home, address = 0, x, y;
vector<int> count_home;

void find() { // 다음 번지 찾는 함수
	int stop = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] && !visit[i][j]) {
				x = i, y = j;
				stop = 1;
				break;
			}
			else x = -1, y = -1;
		}
		if (stop) break;
	}
	return;
}

void dfs(int x, int y) { // dfs로 집 개수 검색
	visit[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (!visit[nx][ny] && map[nx][ny]) {
			dfs(nx, ny);
			home++;
		}
	}
	return;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	
	while (1) {
		find();
		if (x == -1 && y == -1) break;
		home = 1;
		dfs(x, y);
		address++; // 번지 개수 + 1
		count_home.push_back(home); 
	}
	cout << address << "\n"; // 번지 개수 출력
	sort(count_home.begin(), count_home.end()); // 번지별 집 개수 오름차순 정렬
	while (!count_home.empty()) {
		cout << count_home.front() << endl;
		count_home.erase(count_home.begin());
	}
}

dfs가 더 간편한 것 같음