글 읽기 - DFS vs BFS

rlatjrdnjs 6년 전 0

DFS와 BFS로 각각 구현을 해보았는데 하나는 맞고 하나는 틀리게 나옵니다...

push 조건은(DFS의 경우 다음 DFS함수를 호출할 조건, BFS의 경우 다음 위치를 enqueue할 조건)

경계를 나가지 않고 !(x < 0 || y < 0 || x >= N || y >= M) 방문하지 않았을 때 !(map[y][x] > 0) 입니다.

정렬은 순차정렬을 사용했고 코드도 완전히 동일합니다.

어떤 알고리즘이 틀렸는지 바로 아시는분 혹시 있으신가요? 왜 틀렸는지 아시는분 답변 부탁드립니다.

//DFS로 구현
#include <stdio.h>
int N, M, K;
int map[100][100];
int l_x, l_y, r_x, r_y;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int sec_num;
int sec_cnt;
int sec[100000];
void dfs(int x, int y);
int condition(int x, int y);
int main(void) {
	int tmp;
	scanf("%d %d %d", &M, &N, &K);
	for (int i = 0; i < K; ++i) {
		scanf("%d %d %d %d", &l_x, &l_y, &r_x, &r_y);
		for (int y = l_y; y < r_y; ++y) {
			for (int x = l_x; x < r_x; ++x) {
				map[y][x] = 1;
			}
		}
	}
	for (int y = 0; y < M; ++y) {
		for (int x = 0; x < N; ++x) {
			if (map[y][x] == 0) {
				sec_num++;
				sec_cnt = 0;
				dfs(x, y);
				sec[sec_num] = sec_cnt;
			}
		}
	}
	for (int i = 1; i < sec_num + 1; ++i) {
		for (int j = i; j < sec_num + 1; ++j) {
			if (sec[i] > sec[j]) {
				tmp = sec[i];
				sec[i] = sec[j];
				sec[j] = tmp;
			}
		}
	}
	printf("%d\n", sec_num);
	for (int i = 1; i < sec_num + 1; ++i) {
		printf("%d ", sec[i]);
	}
	printf("\n");
	return 0;
}
void dfs(int x, int y) {
	map[y][x] = 1;
	sec_cnt++;
	//printf("cur pos: (%d, %d)\n", x, y);
	for (int i = 0; i < 4; ++i) {
		if (condition(x + dx[i], y + dy[i]) > 0) {
			dfs(x + dx[i], y + dy[i]);
			
		}
	}
}
int condition(int x, int y) {
	if (x < 0 || y < 0 || x >= N || y >= M) {
		return -1;
	}
	else if (map[y][x] > 0) {
		return -1;
	}
	else {
		return 1;
	}
}


=============================================================
//BFS로 구현
#include <stdio.h>
int map[100][100];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
typedef struct pos_ {
	int x;
	int y;
}pos_t;
pos_t queue[10000];
int sector[10000];
int sector_num;
int sec_cnt;
int head, tail;
int M, N, K;
int l_x, l_y, r_x, r_y;

int condition(int x, int y);
int main(void) {
	int x_buf, y_buf, tmp;
	scanf("%d %d %d", &M, &N, &K);
	for (int i = 0; i < K; ++i) {
		scanf("%d %d %d %d", &l_x, &l_y, &r_x, &r_y);
		for (int y = l_y; y < r_y; ++y) {
			for (int x = l_x; x < r_x; ++x) {
				map[y][x] = 1;
			}
		}
	}
	for (int y = 0; y < M; ++y) {
		for (int x = 0; x < N; ++x) {
			if (map[y][x] == 0) {
				sector_num++;
				head = tail = sec_cnt = 0;
				queue[tail].x = x;
				queue[tail++].y = y;
				map[y][x] = sector_num;
				sec_cnt = 1;
			}
			while (head != tail) {
				x_buf = queue[head].x;
				y_buf = queue[head++].y;
				for (int i = 0; i < 4; ++i) {
					if (condition(x_buf + dx[i], y_buf + dy[i]) > 0) {
						queue[tail].x = x_buf + dx[i];
						queue[tail++].y = y_buf + dy[i];
						map[y_buf + dy[i]][x_buf + dx[i]] = sector_num;
						sec_cnt++;
					}
				}
			}
			sector[sector_num] = sec_cnt;
		}
	}
	for (int i = 1; i < sector_num+1; ++i) {
		for (int j = i; j < sector_num+1; ++j) {
			if (sector[i] > sector[j]) {
				tmp = sector[i];
				sector[i] = sector[j];
				sector[j] = tmp;
			}
		}
	}
	printf("%d\n", sector_num);
	for (int i = 1; i < sector_num+1; ++i) {
		printf("%d ", sector[i]);
	}
	printf("%\n");
	return 0;
}
int condition(int x, int y) {
	if (x < 0 || y < 0 || x >= N || y >= M) {
		return -1;
	}
	else if (map[y][x] > 0) {
		return -1;
	}
	else {
		return 1;
	}
}
    
    

kdk8361 6년 전 1

142번 줄 printf 안에 뭔가 이상한 친구가 하나 있는거 같아요.

rlatjrdnjs 6년 전 0

매의 눈이시네요

감사합니다ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

DFS vs BFS

rlatjrdnjs 6년 전 0

kdk8361 6년 전 1

rlatjrdnjs 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말