2667 단지번호붙이기

2667 단지번호 붙이기

Flood-Fill 알고리즘의 대표적인 문제, 연결된 노드의 개수와 전체 묶음의 개수를 출력하는 문제

메모리 효율을 위해 visited 배열을 사용하지 않는 방법을 사용해보았다.

1. 문제

---

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

간단 설명

N * N 입력을 받아, 1의 덩어리가 몇개가 있는지, 그 크기는 몇개인지 출력하는 문제

BFS를 사용한 Flood-Fill의 대표적인 문제다

2. 문제 분석

---

필요변수

1. 맵의 크기 int N
2. 맵을 저장할 배열 int map[26][26] (5<=n<=25>)
3. 4방향 표현할 int direct[4][2] = { 0,-1,-1,0,0,1,1,0 } 배열 (←↑↓→ 방향순으로 트라이)
4. 노드의 좌표를 표현할 struct node{int y; int x;}. pair<int, int>를 써도 상관없을듯
5. 단지의 크기들를 저장할 result vector
   • 단지의 크기를 계산할 int size
6. 단지의 개수를 저장할 int cnt

주의점

• 연속된 숫자로 입력이 주어진다. int 배열에 저장시 한글자씩 나누어 저장 필요
• BFS 들어가면서 map[y][x] = 0 으로 해주면서 단지의 크기를 1 증가시켜줘야함
• result 배열을 오름차순으로 정렬해줘야한다

알고리즘

1. N을 입력받는다
2. N*N 배열 맵을 입력받는다
	- 연속된 숫자를 각 줄별로 입력받아, 한자리수로 끊어 저장한다
3. 단지의 개수를 센다. map에서 1이 나오면 현재 좌표에서 BFS를 호출한다
4. BFS 시작
	4-1. 현재 y,x 좌표를 큐에 넣고, 시작 좌표를 0으로 만든다(방문처리)
	4-2. 단지의 크기를 체크할 변수 size를 정의한다
		- BFS 들어오면서 y, x도 단지에 포함되므로 size를 1로 만든다
	4-3. 큐가 빌때까지 탐색을 계속한다
		4-3-1. 큐의 맨 앞의 노드를 꺼내어 다음 탐색할 노드로 정한다
		4-3-2. 다음 탐색할 노드의 4방향으로 탐색한다
		4-3-3. 맵을 벗어났다면 패스
		4-3-4. 집이 없는곳이라면 패스
		4-3-4. 위 조건들을 패스했다면
			- 다음 탐색할 노드를 방문처리한다 
			- 큐에 다음 탐색할 노드를 넣는다
			- 단지의 크기를 + 1 더해준다
	4-4. 큐가 비었다면, result 벡터에 단지의 크기 size를 뒤에 넣는다
5. 모든 맵의 탐색이 끝났다면 단지의 개수를 출력한다
6. result 배열을 오름차순으로 정렬한다
7. result 배열의 원소를 출력한다

3. 소스코드

---

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define MAX 26

using namespace std;

int N;
int map[MAX][MAX];

int direct[4][2] = { 0,-1,-1,0,0,1,1,0 };

struct node {
	int y;
	int x;
};

vector<int> result;

void BFS(int y, int x) {
	queue<node> qu;
	qu.push({ y, x });
	map[y][x] = 0; // 시작 가라앉히기 
	int size = 0; // 시작칸도 체크
	size++; 

	while (!qu.empty()) {
		node now = qu.front();
		qu.pop();

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.y;
			int dx = direct[t][1] + now.x;

			if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue; // 경계처리
			if (map[dy][dx] == 0) continue; // 집이 없는 곳

			map[dy][dx] = 0; // 다른 칸도 가라앉힌다
			qu.push({ dy, dx });
			size++;
		}
	}
	result.push_back(size);
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	
	cin >> N;

	for (int y = 0; y < N; y++) {
		string s;
		cin >> s;
		for (int x = 0; x < N; x++) {
			map[y][x] = s[x] - '0';
		}
	}
	int cnt = 0;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == 1) {
				BFS(y, x);
				cnt++;
			}
		}
	}
	cout << cnt << "\n";
	sort(result.begin(), result.end(), less<>());
	for (auto e : result) {
		cout << e << "\n";
	}
	
	return 0;
}