글 읽기 - bfs로 풀었는데 시간초과.. 무엇이 문제일까요?

kiyoon123 4년 전 0

bfs로 풀었습니다

정말 정직하게 트리 레벨별로 훑으면서 내려갔구요

중복 탐색 방지하려고 배열 선언했습니디ㅏ

아직 시간 복잡도 개념이 제가 안잡힌건가...

다른 풀이 보니깐 저처럼 한 레벨씩 안하고 큐로 넣고 빼고 한개씩 하는 것도 있던데

그거랑 제가 코딩한거랑 제가 보기엔 시간은 같아 보이는데 왜 시간 초과가 날까요

아님 제가 시간 복잡도 아직 못 파악하는 건가요

#include<iostream>
#include<queue>
#include <algorithm>
using namespace std;

int main() {
	int num;
	cin >> num;
	queue<int> q;
	q.push(num);
	int cnt = 0;
	int tmp;
	bool visited[1000001] = { false, }; //탐색했던 숫자를 재 탐색하지 않도록 하게 해주는 확인 배열

	while (1) {
		int qs = q.size(); //레벨 별 숫자들의 갯수 큐값 측정을 통한 qs로 책정
		cnt++;
		for (int i = 0; i < qs; i++) {
			tmp = q.front();
			q.pop();
			if (!visited[tmp/3] && tmp % 3 == 0) { //탐색했던 숫자 인지 확인 
				if (tmp / 3 == 1) {
					cout << cnt; //카운트 수 출력 바로 프로그램 종료
					return 0;
				}
				else {
					q.push(tmp / 3);
				}
			}
			if (!visited[tmp/2] && tmp % 2 == 0) {
				if (tmp / 2 == 1) {
					cout << cnt;
					return 0;
				}
				else {
					q.push(tmp / 2);
				}
			}
			if (!visited[tmp - 1]) {
				if (tmp - 1 == 1) {
					cout << cnt;
					return 0;
				}
				else
					q.push(tmp - 1);
			}

			visited[tmp] = true;
		}

	}

}

djm03178 4년 전 1

BFS는 큐에서 뺀 뒤가 아닌 큐에 넣을 때 방문 표시를 해야 중복 방문이 일어나지 않습니다.

wjddydgns99 4년 전 2

while()문 안에 3개의 q.push()에서 각각 모두 visited=true 해주어야 할 것 같아요.

저렇게하면 재방문해서 시간초과 뜰거에요.

kiyoon123 4년 전 0

visited[tmp/3] = true

visited[tmp/2] = true

visited[tmp-1] = true

모두 push밑에 해주었는데도 시간 초과가 나네요.... 뭐죠..도저히 머리를 굴려도 모르겠네요

djm03178 4년 전 2

1 넣으면 안 끝날 것 같네요.

kiyoon123 4년 전 0

1이 문제였네요 ㅠㅠ 감사합니다.. ㅠㅠ

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

문제

문제

출처

ICPC

bfs로 풀었는데 시간초과.. 무엇이 문제일까요?

kiyoon123 4년 전 0

djm03178 4년 전 1

wjddydgns99 4년 전 2

kiyoon123 4년 전 0

djm03178 4년 전 2

kiyoon123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말