BOJ/백준 2667번 단지번호붙이기

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

2667번: 단지번호붙이기

 

언어 : C++

환경 : Visual Studio 2019

 

이 문제는 BFS나 DFS로 풀 수 있는 있는 문제입니다.

설명은 코드에 주석으로 달려있습니다.

 

BFS 풀이

#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
#define X first
#define Y second
int dx[4] = { 1,0,-1,0 }; // 아래, 위         //                   (cur.X - 1,cur.Y)
int dy[4] = { 0,1,0,-1 }; // 우측, 좌측       // (cur.X, cur.Y - 1)( cur.X  ,cur.Y )(cur.X, cur.Y + 1)
string board[26];                            //                   (cur.X + 1,cur.Y)
int dis[25][25];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	queue <pair<int, int>> Q;
	vector<int> ans;
	int n, sector_no = 0; // sector_no는 각 구역에 번호를 매기는 변수이다
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> board[i];
	}
	int len = board->length();
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			if (board[i][j] != '0' && dis[i][j] == 0) { // board가 0이 아니면 방문해야하는 칸임을 의미 dis가 0이면 아직 방문안한 칸이라는 의미
				int cnt = 1; // 방문하지 않은 장소를 방문했으면 일단 1개는 발견한것이기 때문에 0 아닌 1로 초기화를 한다
				Q.push({ i,j });
				dis[i][j] = ++sector_no; // 새로운 구역이니 번호를 하나 증가 시켜준다
				while (!Q.empty()) { // BFS
					pair<int, int> cur = Q.front(); Q.pop();
					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir];
						if (nx < 0 || nx >= len || ny < 0 || ny >= len) continue;
						if (board[nx][ny] != '1' || dis[nx][ny] != 0) continue; // 보드가 '1'이 아니면 0이기 때문에 방문 할 수 없음. dis가 0이 아니면 이미 방문한 장소임.
						dis[nx][ny] = sector_no;  // 방문한 장소에 구역 no를 붙여줌
						Q.push({ nx,ny }); cnt++; // 새 장소를 방문 했으니 cnt++
					}
				}
				ans.push_back(cnt); // 한 단지의 방문이 끝나면 cnt를 vector에 넣어줌
			}
		}
	}
	int size = ans.size();
	sort(ans.begin(), ans.end()); // 정렬
	cout << size << '\n';
	for (int i = 0; i < size; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

 

DFS는 단순 Queue를 Stack로 바꿨을 뿐이라 따로 설명을 적지는 않겠습니다.

 

DFS 풀이

#include <iostream>
#include <utility>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;
#define X first
#define Y second
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
string board[26];
int dis[25][25];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	stack <pair<int, int>> S;
	vector<int> ans;
	int n, sector_no = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> board[i];
	}
	int len = board->length();
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			if (board[i][j] != '0' && dis[i][j] == 0) {
				int cnt = 1;
				S.push({ i,j });
				dis[i][j] = ++sector_no;
				while (!S.empty()) { // DFS
					pair<int, int> cur = S.top(); S.pop();
					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir];
						if (nx < 0 || nx >= len || ny < 0 || ny >= len) continue;
						if (board[nx][ny] != '1' || dis[nx][ny] != 0) continue;
						dis[nx][ny] = sector_no;
						S.push({ nx,ny }); cnt++;
					}
				}
				ans.push_back(cnt);
			}
		}
	}
	int size = ans.size();
	sort(ans.begin(), ans.end());
	cout << size << '\n';
	for (int i = 0; i < size; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

결과

참고로 이 문제를 풀 때는 C++의 string 클래스나 C-string으로 푸는 것을 추천합니다.
이 문제는 입력을 받을 때 공백 없이 입력을 받기 때문입니다.

그리고 마지막으로 str.length() 같은 함수는 미리 정수형 변수에 반환 값을 넣어서 사용하는 걸 권장합니다.
반복할 때마다 호출하면 터지기 딱 좋아요.