BOJ 2667 단지번호붙이기

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

1. 문제요약

- N*N 맵, 5 <= N <= 25

- 0 빈공간 / 1 집

- 상하좌우로 연결된 집을 하나의 단지

- 단지의 갯수와 각 단지별 집의 갯수를 오름차순으로 출력

2. 접근방법

- 방문한적이 없고, 집이면 방문해서 상하좌우로 연결된 모든집을 방문하여 단지를 만듬

- 단지를 만들면서 집의 갯수를 같이 셈

- bfs / dfs 모두 가능

3. 시간복잡도

- 모든 칸을 한번씩 방문하므로 N^2 = 625

4. 회고

- 전역변수를 안쓰고 리턴값을 쓰니까 조금 귀찮기는 한데 초기화를 안해도 되서 

- 나름의 장단점이 있는데 음...

- 방문한 집이면 맵 자체를 1 -> 0 으로 바꾸면 check 배열을 안써도 됨

- cin 만 쓰려니 공백없는 정수를 받을때는 불편함...

- sort 없이 1차원 배열을 최대 집 갯수 만큼 선언해서 단지 갯수를 입력함.

a[집 갯수] = 단지 갯수
for(int i = 0; i < n*n + 1; i++){
    for(int j = 0; j < a[i]; j++){
        cout << i << "\n";
    }
}

18.2.7

소스코드 수정 - num이 필요없잖아.. 벡터를 쓰는데

dfs만 수정함

소스코드 : dfs

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;
vector<int> house;
char map[25][25];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int dfs(int row, int col){
	map[row][col] = '0';

	int ret = 1, nr, nc;
	for (int i = 0; i < 4; i++){
		nr = row + dx[i];
		nc = col + dy[i];

		if (0 <= nr && nr < n && 0 <= nc && nc < n && map[nr][nc] == '1')
			ret += dfs(nr, nc);
	}
	return ret;
}

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (map[i][j] == '1')
				house.push_back(dfs(i, j));

	sort(house.begin(), house.end());
	cout << house.size() << "\n";
	for (int i = 0; i < house.size(); i++)
		cout << house.at(i) << "\n";
	return 0;
}

소스코드 : bfs

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int n, check[25][25];
char map[25][25];
vector<int> house;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	queue<pair<int, int>> q;
	
	int num = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			int cnt = 0;
			if (!check[i][j] && map[i][j] == '1'){
				q.push(make_pair(i, j));
				check[i][j] = true;
				num++; cnt++;

				while (!q.empty()){
					int x = q.front().first;
					int y = q.front().second;
					q.pop();

					int nx, ny;
					for (int k = 0; k < 4; k++){
						nx = x + dx[k];
						ny = y + dy[k];

						if (0 <= nx && nx < n && 0 <= ny && ny < n
							&& !check[nx][ny] && map[nx][ny] == '1'){
							check[nx][ny] = true;
							cnt++;
							q.push(make_pair(nx, ny));
						}
					}
				}
				house.push_back(cnt);
			}
		}
	}
	sort(house.begin(), house.end());
	cout << num << "\n";
	for (int i = 0; i < house.size(); i++)
		cout << house.at(i) << "\n";
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]