글 읽기 - 왜 bfs는 안되고 Floyd는 되는지 궁금합니다....

blackbbean 5년 전 0

자료구조를 배울때,

Floyd보다 더 빠르다고 배웠는데요 (O(V^2) / O(V^3))

왜, 이 문제에서 Floyd는 되고 BFS는 되지 않는지 궁금합니다.

방향이 고정되지 않아 앞 뒤로 가야하는 상황이 넓이를 크게 만들어서 BFS를 돌릴수없는건가요...?

또, 어떤 감으로(?) 어떤 근거로(?)

이 문제는 Floyd로 접근해야한다! 가 도출되는지 궁금합니다..

사실 전 DFS보단 BFS가 일반적으로 빠르니까 BFS를 결정했거든요.

한번에 앞,뒤로 가는 데이터 검사도 용이하다 생각했고요..

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int nodelist[401];
int map[401][401];
int n, k;
int a, b;
int s;

int bfs(int start,int goal) {
	queue<pair<int,int>> q;
	int visited[401];
	memset(visited, 0, sizeof(visited));
	visited[start] = 1;
	q.push({ start,0 });
	while (!q.empty()) {
		int pd = q.front().first;
		if (pd == goal) {
			return q.front().second;
		}
		q.pop();
		//BFS 앞으로 탈때
		for (int i = 1; i <= n; i++) {
			if (map[pd][i] == 1 && visited[i] == 0) {
				visited[i] = 1;
				q.push({ i,-1 });
			}
		}
		//BFS 뒤로 탈때 
		for (int i = 1; i <= n; i++) {
			if (map[i][pd] == 1 && visited[i] == 0) {
				visited[i] = 1;
				q.push({i, 1});
			}
		}
	}
	return 0;
}
int main() {
	scanf("%d %d", &n, &k);
	for (int i = 0; i < k; i++) {
		scanf("%d %d", &a, &b);
		map[a][b] = 1;
		nodelist[a] = 1;
		nodelist[b] = 1;
	}
	scanf("%d", &s);
	for (int i = 0; i < s; i++) {
		scanf("%d %d", &a, &b);
		if (nodelist[a] == 0 || nodelist[b] == 0) {
			printf("0\n");
		}
		else {
			printf("%d\n", bfs(a, b));
		}
	}
}

luniro 5년 전 2

한가지 케이스면 BFS가 빠른 것이 맞습니다

하지만 Floyd는 한 번만 수행하면 각 케이스에 대해 O(1)로 찾아낼 수 있으므로, O(V^3)이 되지만,

BFS의 경우에는 각 케이스에 대해 O(V^2)이므로 총 시간복잡도는 (SV^2)이 되고, 여기서 최악의 경우 V = 400 S = 50000이므로 시간초과가 발생할 여지가 있습니다

blackbbean 5년 전 1

감사합니다 이해하였습니다. !

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

문제

문제

출처

ICPC

왜 bfs는 안되고 Floyd는 되는지 궁금합니다....

blackbbean 5년 전 0

luniro 5년 전 2

blackbbean 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말