글 읽기 - bfs로 짜니까 메모리초과 문제 ㅠㅠ

sm0819 6년 전 0

bfs로 다시 짜니까 메모리초과 뜨는데 어떻게 하나요ㅠㅠ dfs는 시간초과 뜨고..ㅠㅠ

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

vector <vector <int> > v;
int d[1001];
int _max;
int T, N, K, W;

struct Node
{
	int i;
	int total;
};

void bfs(int n, int total)
{
	queue <Node> q;
	Node t;
	t.i = n;
	t.total = total;
	q.push(t);
	
	while (!q.empty())
	{
		int i = q.front().i;
		int total = q.front().total;
		q.pop();

		if (!v[i].size())
		{
			if (_max < total)
				_max = total;
			continue;
		}

		for (auto j : v[i])
		{
			Node t;
			t.i = j;
			t.total = total + d[j];
			q.push(t);
		}

	}
}

int main()
{
	cin >> T;
	
	for (int t = 1; t <= T; t++)
	{
		cin >> N >> K;
		
		for (int i = 1; i <= N; i++)
		{
			cin >> d[i];
		}
	
		v = vector < vector <int> > (N+1);
		for (int i = 1; i <= K; i++)
		{
			int x, y;
			cin >> x >> y;
			v[y].push_back(x); // 반대로 넣어서 찾는다
		}

		cin >> W;

		bfs(W, d[W]);
	
		cout << _max << endl;
		_max = 0;
	}

	return 0;
}


/* dfs
#include <iostream>
#include <vector>

using namespace std;

vector <vector <int> > v;
int d[1001];
int _max;
int T, N, K, W;

void dfs(int n, int total)
{
	if (!v[n].size())
	{
		if(_max < total)
			_max = total;
	}
	for (auto i : v[n])
	{
		dfs(i, total+d[i]);
	}
	
}

int main()
{
	cin >> T;
	
	for (int t = 1; t <= T; t++)
	{
		cin >> N >> K;
		
		for (int i = 1; i <= N; i++)
		{
			cin >> d[i];
		}
	
		v = vector < vector <int> > (N+1);
		for (int i = 1; i <= K; i++)
		{
			int x, y;
			cin >> x >> y;
			v[y].push_back(x); // 반대로 넣어서 찾는다
		}

		cin >> W;

		dfs(W, d[W]);
	
		cout << _max << endl;
		_max = 0;
	}

	return 0;
}*/

jh05013 6년 전 0

30줄에 cout << i << endl;를 넣어 보시면 dfs때와 마찬가지로 중복호출이 발생한다는 걸 확인할 수 있습니다.

sm0819 6년 전 0

넵! 한번 수정해보겠습니다 답변감사합니다.

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

문제

문제

출처

ICPC

bfs로 짜니까 메모리초과 문제 ㅠㅠ

sm0819 6년 전 0

jh05013 6년 전 0

sm0819 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말