[C++] [BFS, DFS] 백준 2667번 : 단지번호붙이기

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

2667번: 단지번호붙이기

BFS 풀이 - 메모리 초과

#include<queue>
#include<utility>
#include<algorithm>
#include<stdio.h>

int direct[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };	//이동방향
int danzi_num = 2;	//단지번호
int N;	//map넓이
int map[25][25];	//맵

void bfs() {
	queue<pair<int, int>> Q;

	while (1) {
		//탐색시작점 (map 에서 값이 1인곳) 찾기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1) {
					Q.push(make_pair(i, j));
					goto EXIT;
				}
				//맵에서 1인곳이 없다면(탐색을 모두 끝마쳤으면) return;
				if (i == N - 1 && j == N - 1)
					return;
			}
		}
		EXIT:

		while (!Q.empty()) {
			pair<int, int> Now = Q.front();
			Q.pop();
			map[Now.first][Now.second] = danzi_num;

			for (int i = 0; i < 4; i++) {
				int dy = Now.first + direct[i][0];
				int dx = Now.second + direct[i][1];

				if (0 <= dy && dy < N && 0 <= dx && dx < N && map[dy][dx] == 1)
					Q.push(make_pair(dy, dx));
			}
		}
		danzi_num++;	//탐색 끝, 다음탐색시 단지번호 표시를 위한 변수++
	}
}

int main(void) {
	//입력
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			scanf("%1d", &map[i][j]);
	}

	bfs();	//너비우선탐색

	int *danzi = new int[danzi_num]();

	//출력
	cout << danzi_num - 2 << endl;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			if(map[i][j] != 0)
				danzi[map[i][j]]++;
	}
	sort(danzi, danzi + danzi_num);
	for (int i = 2; i < danzi_num; i++)
		cout << danzi[i] << endl;
}

 

DFS 풀이 - 정답

#include<algorithm>
#include<utility>
#include<stdio.h>

int direct[4][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };	//이동방향
int danzi_num = 2;	//단지번호
int N;	//map넓이
int map[25][25];	//맵

void dfs(pair<int, int> x) {
	if (map[x.first][x.second] != 1)	return;
	map[x.first][x.second] = danzi_num;

	for (int i = 0; i < 4; i++) {
		int dy = x.first + direct[i][0];
		int dx = x.second + direct[i][1];

		if (0 <= dx && dx < N && 0 <= dy && dy < N && map[dy][dx] == 1) {
			pair<int, int> Now(dy, dx);
			dfs(Now);
		}
	}
}

void findDanzi() {
	pair<int, int> Start;
	while (1) {
		//탐색시작점 (map 에서 값이 1인곳) 찾기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1) {
					Start = make_pair(i, j);	//시작점 기록
					goto EXIT;
				}
				//맵에서 1인곳이 없다면(탐색을 모두 끝마쳤으면) return;
				if (i == N - 1 && j == N - 1)
					return;
			}
		}
	EXIT:
		dfs(Start);	//깊이우선탐색
		danzi_num++;
	}
}

int main(void) {
	//입력
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			scanf("%1d", &map[i][j]);
	}

	findDanzi();

	int *danzi = new int[danzi_num]();

	//출력
	cout << danzi_num - 2 << endl;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			if (map[i][j] != 0)
				danzi[map[i][j]]++;
	}
	sort(danzi, danzi + danzi_num);
	for (int i = 2; i < danzi_num; i++)
		cout << danzi[i] << endl;
}