글 읽기 - 메모리 초과면 큐가 꽉차는거같은데;;;

dhedaa 6년 전 0

출발점에서 해당거리만큼 이동하면 그 좌표를 큐에 넣고

bfs를 돌려서 큐에 목적지인 n-1, n-1이 들어오면 count를 증가시키는 방법으로 코드를 짰는데요

문제에서 도착방법의 수가 2^63-1 보다 작거나 같다고 하는데

그러면 큐를 어떻게 써줘야 저 크기만큼 메모리를 수용할 수 있는거죠?ㅠ

#include <iostream>
#include <queue>

using namespace std;
int n, cnt;
int map[100][100];
queue<pair<int, int>> q;

void bfs(int x, int y)
{	
	q.push(make_pair(x, y));
	while (!q.empty())
	{	
		int a = q.front().first;
		int b = q.front().second;		
		q.pop();		
		if (a == n - 1 && b == n - 1)
		{			
			cnt++;	
			continue;
		}		
		int nx =  a + map[b][a];
		int ny =  b + map[b][a];		
		if (nx < n)
		{			
			q.push(make_pair(nx, b));
		}
		if (ny < n)
		{			
			q.push(make_pair(a, ny));
		}		
	}
	cout << cnt << endl;
}

int main()
{	
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &map[i][j]);			
		}			
	}	
	bfs(0, 0);		
}

subinium 6년 전 2

오른쪽과 아래로 이동할 수 밖에 없다는 조건을 이용하면 BFS가 아니라 DP로 풀 수 있을거에요.

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

문제

문제

출처

ICPC

메모리 초과면 큐가 꽉차는거같은데;;;

dhedaa 6년 전 0

subinium 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말