글 읽기 - [11724 연결 요소의 개수] bfs, dfs 시간차이 질문드립니다!!

sukth09 5년 전 0

1부터 N개의 노드를 방문하면서 연결되어 있는 노드들을 다 방문하면서

방문여부를 체크해주고 각 dfs, bfs를 나오면 연결요소의 개수를 1개씩 증가시키는 알고리즘입니다.

제가 생각했을 때, dfs 와 bfs의 처리방식은 같다고 생각되는데,

bfs는 1204ms 시간이 소요되고

dfs는 260ms 시간이 소요됩니다.

대체 왜 시간이 1초씩이나 차이나는지 이유를 모르겠습니다 ㅠㅠ 도와주세요

아니면 제가 간과하고 있는 부분이 있을까요?

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

// #define TESTCASE

static int T, N, M, arr[1001][1001]; 
// N : 정점개수, M : 간선개수, arr : 인접배열
static int ans, chk[1001];
// ans : 연결요소개수, chk : 방문여부
static queue<int> q;
// bfs를 위한 q

static void dfs(int idx) {
	if(chk[idx]) return;
    // 이미 방문했다면 종료

	chk[idx] = 1;
    // 방문체크
	for(int i = 1; i <= N; i++) {
		if(chk[i] || !arr[idx][i]) continue;
        // 이미 방문했거나 idx와 i 사이에 간선이 없다면 continue
		dfs(i);
        // 아니면 노드 방문
	}
}
static void bfs(void) {
	while(!q.empty()) {
		int c = q.front();
		q.pop();
        // q에서 현재 노드 pop
		chk[c] = 1;
        // 방문체크
		for(int i = 1; i <= N; i++) {
			if(chk[i] || !arr[c][i]) continue;
            // 이미 방문했거나 idx와 i 사이에 간선이 없다면 continue
			q.push(i);
            // 아니면 노드 push
		}
	}
}
static void init(void) {
	ans = 0;
	memset(arr, 0, sizeof(arr));
	memset(chk, 0, sizeof(chk));
    // 초기화
}
static void scan(void) {
	cin >> N >> M;
	for(int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		arr[u][v] = 1;
		arr[v][u] = 1;
        // 인접배열에 간선 체크
	}
}
static void solve(void) {
	for(int i = 1; i <= N; i++) {
		if(chk[i]) continue;
        
        // dfs(i);
        
		q.push(i);
		bfs();
        
		ans++;
	}
}
int main(void) {
#ifdef TESTCASE
	freopen("sample_input.txt", "rb", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++) {
#endif
		init();
		scan();
		solve();
		printf("%d\n", ans);
#ifdef TESTCASE
	}
	fclose(stdin);
#endif
	return 0;
}

djm03178 5년 전 0

방문 체크는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 해야 중복 방문을 하지 않습니다. 여러 정점에서 한 정점으로 동시에 들어가려고 할 수 있기 때문입니다.

그나저나 그게 시간 초과가 아니라니, 데이터 추가를 요청해야 할 것 같습니다.

sukth09 5년 전 0

아하!

매번 답변 감사합니다!! 다시한번 제출해보겠습니다

sukth09 5년 전 0

다시재출해보니 같은 시간으로 나오네요!!

하나배워갑니다 감사합니다!!

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

문제

문제

출처

ICPC

[11724 연결 요소의 개수] bfs, dfs 시간차이 질문드립니다!!

sukth09 5년 전 0

djm03178 5년 전 0

sukth09 5년 전 0

sukth09 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말