글 읽기 - BFS로 알고리즘 짰는데 시간초과가 뜹니다. 도와주세요

tera1130 8년 전 0

BFS로 알고리즘 짰는데 시간초과라고 뜨네요...

어느 부분이 시간이 많이 걸리는걸까요? queue를 직접 안짜고 STL queue 를 써서 그런건가요?

시간초과가 자꾸 떠서 알고리즘을 제대로 짠건지 아닌지도 모르겠네요 ㅜㅜ

#include <iostream>
#include <queue>
using namespace std;
void maze_search(queue<int*>* process, int* count);

int main()
{
	int n, m;
	queue<int*> process;
	cin >> n >> m;
	int maze[102][102] = { 0, };
	int count = 1;
	int input_h = 0;
	char str[100];
	for (int i = 1; i <= n; i++) {
		cin >> str;
		input_h = m;
		while (input_h>= 1) {
			maze[i][input_h] = (str[input_h - 1] - '0');
			input_h--;
		}
	}
	process.push(&maze[1][1]);
	while (process.front() != &maze[n][m]){
		int a = process.size();
		while (a > 0){
			maze_search(&process, &count);
			a--;
		}
		count += 1;
	}
	cout << count;
}

void maze_search(queue<int*>* process, int* count){
	if (*((*process).front() + 1) == 1){
		(*process).push((*process).front() + 1);
	}
	if (*((*process).front() - 1) == 1){
		(*process).push((*process).front() - 1);
	}
	if (*((*process).front() + 102) == 1){
		(*process).push((*process).front() + 102);
	}
	if (*((*process).front() - 102) == 1){
		(*process).push((*process).front() - 102);
	}
	*(*process).front() = 0;
	(*process).pop();
}

pl0892029 8년 전 0

방문한 곳에 대한 체크는 하지 않으신것 같은데, 확인해보시겠어요?

tera1130 8년 전 0

visit으로 방문 표시 대신에 이미 방문한 곳은 0을 대입해서 가지 못하도록 했습니다.

pl0892029 8년 전 0

0 0 -> 0 1 -> 1 1

0 0 -> 1 0 -> 1 1

은 같은 깊이라서 중복해서 들어갈 수 있을거 같은데... 확인해보시겠어요?

pl0892029 8년 전 0

2개의 값늘 queue를 통해서 관리하기 위해서 포인터를 사용하신 것으로 보이네요.

포인터를 쓰는 것보다 구조체를 이용하시면 어떨까 추천드리는 바입니다.

물론 위에서처럼 0으로 만드는 것보다는 체크 배열을 만들어서 방문 체크를 하는게 더 깔끔하다 생각되네요.

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

문제

문제

출처

ICPC

BFS로 알고리즘 짰는데 시간초과가 뜹니다. 도와주세요

tera1130 8년 전 0

pl0892029 8년 전 0

tera1130 8년 전 0

pl0892029 8년 전 0

pl0892029 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말