글 읽기 - c++) 17071번 숨바꼭질5 bfs문제 메모리 초과

leewwo2o 5년 전 0

메모리 초과가 뜹니다. 숫자가 커지면 큐에 너무 많은 수를 넣게 되서 그런 것 같아서 이런 방식으로 풀면 안될것 같은데 어떻게 풀어야 할까요?

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int a;
queue<int> qu;
int bfs(int n, int k, int ti) {
	int z = 1;
	qu.push(n);
	while (qu.size()) {
		if (k > 500000) {
			return -1;
		}
		int siz = qu.size();   
		for (int i = 0; i < siz; i++) {//큐 사이즈만큼 검사를 함
			a = qu.front();
			if (a == k)
				return ti;
			qu.pop();
			if (a - 1 >= 0) {
				qu.push(a - 1);
			}
			if (a + 1 <= 500000) {
				qu.push(a + 1);
			}
			if (a * 2 <= 500000) {
				qu.push(a * 2);
			}                     //큐에 집어넣어서 이동할 수 있는 경우의 수를 넣어줍니다
		}
		k += z;  //동생 이동 시키는것
		z++;
		ti++;  //시간 더함
	}
	return ti;
}
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int n, k, mi, ti = 0;
	cin >> n >> k;
	if (n == k) {
		cout << 0;
		return ti;
	}
	mi = bfs(n, k, ti);
	cout << mi;
	return 0;
}

djm03178 5년 전 0

모든 BFS는 반드시, 반드시 방문 체크를 해야만 합니다. 안 그러면 큐에 같은 원소가 여럿 들어가게 되고 그 원소들이 더 많이 중복된 원소를 만들어내고... 가 반복되어 지수복잡도에 달하는 원소를 큐에 넣게 됩니다.

물론 이 문제는 그 특성상 단순히 칸마다 방문 체크를 해서는 해결할 수 없습니다. 다른 질문들을 참고해 보세요.

leewwo2o 5년 전 0

답변 감사합니다 생각해 봐야겠네요

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

문제

문제

출처

ICPC

c++) 17071번 숨바꼭질5 bfs문제 메모리 초과

leewwo2o 5년 전 0

djm03178 5년 전 0

leewwo2o 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말