글 읽기 - bfs 메모리 초과 질문드립니다.

112ckek 4년 전 0

안녕하세요.

ans에 자취를 기록하는 방법으로 풀어봤는데 메모리 초과가 나네요.

5 17의 경우

ans[5]에는 5

ans[4]에는 5 4

ans[8]에는 5 4 8

ans[16]에는 5 4 8 16

ans[17]에는 5 4 8 16 17

이런식으로 자취를 기록하도록 하고 큐에 넣을 때 체크하도록 했는데 메모리 초과가 어디서나는지 궁금합니다.

도움 주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool check[100001];
vector<int> list[100001];	// 인접리스트
vector<int> ans[100001];	// 자취를 기록하는 배열

void bfs(int from, int k){
	queue<int> q;
	q.push(from);
	check[from] = true;
	ans[from].push_back(from);	
	while(!q.empty()){
		from = q.front();
		q.pop();
		for(int to: list[from]){
			if(check[to]) continue;
			q.push(to);
			check[to] = true;
			int size = ans[from].size();
			for(int i = 0; i < size; i++){	// 자취 복사
				ans[to].push_back(ans[from][i]);
			}
			ans[to].push_back(to);	// 자취 추가
			if(to == k) return;
		}
	}
	return;
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, K; cin >> N >> K;
	for(int i = 0; i <= 100001; i++){	// 인접리스트 채우기
		if(i + 1 <= 100001) list[i].push_back(i + 1);
		if(i - 1 >= 0) list[i].push_back(i - 1);
		if(2 * i <= 100001) list[i].push_back(2 * i);
	}
	bfs(N, K);
	int size = ans[K].size();
	cout << size - 1 << '\n';
	for(int i = 0; i < size; i++){
		cout << ans[K][i] << ' ';
	}
	return 0;	
}

djm03178 4년 전 4

자취를 전부 기록하면 O(N)개의 점 각각에 대해 길이 O(N)의 자취가 남으니까 O(N^2)의 메모리를 필요로 하게 되므로 당연히 메모리 초과입니다.

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

문제

문제

출처

ICPC

bfs 메모리 초과 질문드립니다.

112ckek 4년 전 0

djm03178 4년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말