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

 

 

 

 

BFS와 DFS 두가지로 다 가능한 방법이다.

처음에 관련 포스팅을 참고하여 DFS로 푼후,  BFS로도 풀어보았다.

 

 

 

<중요포인트>

1. 입력받은 N*N을 돌면서 1이고 방문하지 않은 곳일 경우 DFS or BFS함수를 호출한다.

2. 호출된 DFS함수는 '재귀'로 연결된 모든 곳을 찾으면서 cnt++하고 더이상 연결된 곳이 없어서 함수실행을 마친후엔  vector에 그 cnt(연결된 마을수)를 push_back 한다.

2-1. 호출된 BFS 함수는 '큐'로 연결된 모든 곳을 찾는다. while문 안에서 현재위치와 연결된 모든 곳을 큐에 넣고 현재위 치를 pop 한후의 front가 현재위치가 되어 연결된 곳이 더이상 없어 큐가 빌때 까지 반복한다.

 

 

 

 

 

1. DFS

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
//#include <cstring> //memset
using namespace std;

const int MAX = 25;

typedef struct {
	int y, x;
}Dir;

Dir moveDir[4] = { {1,0},{-1,0},{0,1},{0,-1} };

int N;
int cnt;	// 각 단지 내 집 수 
string graph[MAX];
vector<int> residance;	// 단지 내 집 수 저장용 벡터
bool visited[MAX][MAX];

void DFS(int y, int x) {
	cnt++;
	visited[y][x] = true;

	for (int i = 0; i < 4; i++) {

		int nextY = y + moveDir[i].y;
		int nextX = x + moveDir[i].x;

		if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) {
			if (graph[nextY][nextX] == '1' && visited[nextY][nextX] == false) {
				DFS(nextY, nextX);
			}
		}
	}
}


int main(void) {

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> graph[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (graph[i][j] == '1' && visited[i][j] == false) {
				cnt = 0;
				DFS(i, j);
				residance.push_back(cnt);
			}
		}
	}

	sort(residance.begin(), residance.end());
	cout << residance.size() << endl;

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

 

 

 

 

 

2. BFS

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
//#include <cstring> //memset
using namespace std;

const int MAX = 25;

typedef struct {
	int y, x;
}Dir;

Dir moveDir[4] = { {1,0},{-1,0},{0,1},{0,-1} };

int N;
int cnt;	// 각 단지 내 집 수 

string graph[MAX];
vector<int> residance;	// 단지 내 집 수 저장용 벡터
bool visited[MAX][MAX];

void BFS(int y, int x) {
	queue<Dir> q;
	Dir start = { y, x };
	q.push(start);
	visited[y][x] = true;

	while (!q.empty()) {
		y = q.front().y;
		x = q.front().x;
		q.pop();
		cnt++;

		for (int i = 0; i < 4; i++) {
			int nextY = y + moveDir[i].y;
			int nextX = x + moveDir[i].x;

			if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) {
				if (graph[nextY][nextX] == '1' && visited[nextY][nextX] == false) {
					Dir pu = { nextY, nextX };
					q.push(pu);
					visited[nextY][nextX] = true;
				}
			}
		}
		
	}
}


int main(void) {

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> graph[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (graph[i][j] == '1' && visited[i][j] == false) {
				cnt = 0;
				BFS(i, j);
				residance.push_back(cnt);
			}
		}
	}

	sort(residance.begin(), residance.end());
	cout << residance.size() << endl;

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

	return 0;
	
}