글 읽기 - bfs로 사이클 판별할 수 있나요? 시간초과 이유도좀 봐주시면 감사하겠습니다.

bk8540 4년 전 0

사이클 판별은 dfs로 푸는방법은 많이 나와있지만 bfs로는 없더라구요

아예 사이클 판별할때는 dfs로만 해야하는 건지 궁굼합니당.

그리고 이코드에서지금 시간초과가 나는데 그 이유가 무엇인지 ㅠㅠ

50*50 이여서 깊이가 최대 2500까지 가는거 같은데 이정도깊이면 시간초과가 뜨는건가요 ??

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
#include <functional>
#include <utility>
using namespace std;
int inf = 10000;
int dist[50][50], n, m;
int side[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };
char map[50][50];
int bfs(int r, int c) {
	// 사이클 판별? dfs로 풀기
	dist[r][c] = true;
	queue<pair<int, int>>q;
	q.push({ r,c });
	int maxv = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (dist[x][y] >= inf)return -1;

		for (int d = 0; d < 4; ++d) {
			int nx = x + side[d][0] * (int)(map[x][y] - '0');
			int ny = y + side[d][1] * (int)(map[x][y] - '0');

			if (nx < 0 || nx >= n || ny < 0 || ny >= m || map[nx][ny] == 'H')continue;
			
			q.push({ nx,ny });

			dist[nx][ny] = dist[x][y] + 1;

			maxv = max(maxv, dist[nx][ny]);
		}
	}
	return maxv;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	inf = n * m + 2;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> map[i][j];

	cout << bfs(0, 0) << '\n';

	return 0;
}

clrmt 4년 전 1

벨만포드 아이디어를 적용해 최대 사이클 수를 넘지 않도록 한 것 같네요. 풀리기는 할 겁니다. 다만, bfs의 같은 depth에서 중복하여 방문하는것을 빼내는게 좋을 것 같습니다.

10 10

1111111111

이거 시간 내에 돌아가나 봐 주세요. 제가 모바일 컴파일러로 확인하였기 때문에 결과가 달랐을 수 있습니다.

bk8540 4년 전 0

확인했습니다. 감사합니다

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

문제

문제

출처

ICPC

bfs로 사이클 판별할 수 있나요? 시간초과 이유도좀 봐주시면 감사하겠습니다.

bk8540 4년 전 0

clrmt 4년 전 1

bk8540 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말