백준 2667번 : 단지번호붙이기

문제 링크 : www.acmicpc.net/problem/2667

내 풀이(2021.1.13.) : BFS

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

using namespace std;

int N;
vector<int> list;
queue<pair<int, int>> q;
int map[25][25]; // [y][x] 
int visit[25][25]; // [y][x]
int dy[4] = { 0, -1, 0, 1 };
int dx[4] = { -1, 0, 1, 0 };

void bfs(int y, int x) {
	int cnt = 0;
	visit[y][x] = 1;
	q.push(make_pair(y, x));
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop(); cnt++;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (visit[ny][nx] == 1) continue;
			if (map[ny][nx] == 0) continue;
			visit[ny][nx] = 1;
			q.push(make_pair(ny, nx));
		}
	}
	list.push_back(cnt);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	for (int j = 0; j < N; j++) {
		string str; cin >> str;
		for (int i = 0; i < N; i++) {
			map[j][i] = str[i] - '0';
		}
	}
 
	int cnt = 0;
	for (int j = 0; j < N; j++) {
		for (int i = 0; i < N; i++) {
			if (visit[j][i] == 1 || map[j][i] == 0) continue;
			bfs(j, i);
			cnt++;
		}
	}
	sort(list.begin(), list.end());

	cout << cnt << endl;
	for (int i = 0; i < list.size(); i++) {
		cout << list[i] << endl;
	}

	return 0;
}

* 주의 : cin.get()는 space와 개행 문자도 하나의 문자로 취급하여 입력 받는다.
* 주의2 : int number = str[i] - '0'; // str[i]는 char 타입이므로 '0'만큼 차이를 빼주고 나서 int에 대입해야 한다.

 

참고 : simsimjae.tistory.com/33

 

내 풀이2(2021.1.13.) : DFS

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

using namespace std;

int N;
int map[25][25];
int visit[25][25];
int dy[4] = { 0, -1, 0, 1 };
int dx[4] = { -1, 0, 1, 0 };

void dfs(int y, int x, vector<int>& cnt) {
	cnt[cnt.size() - 1]++;
	visit[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		if (visit[ny][nx] == 1) continue;
		if (map[ny][nx] == 0) continue;
		dfs(ny, nx, cnt);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	for (int j = 0; j < N; j++) {
		string str; cin >> str;
		for (int i = 0; i < N; i++) {
			map[j][i] = str[i] - '0';
		}
	}
	
	vector<int> cnt;
	for (int j = 0; j < N; j++) {
		for (int i = 0; i < N; i++) {
			if (visit[j][i] == 1 || map[j][i] == 0) continue;
			cnt.push_back(0);
			dfs(j, i, cnt);
		}
	}
	sort(cnt.begin(), cnt.end());

	cout << cnt.size() << endl;
	for (int i = 0; i < cnt.size(); i++) {
		cout << cnt[i] << endl;
	}

	return 0;
}