글 읽기 - BFS안되는이유, 유사 Dp추천부탁드려요

ezelay 8년 전 0

아래에 코드 2개를 연달아 올렸습니다.

윗 코드는 BFS코드이고 아래는 DP로 풀었는데

처음에 BFS로 했더니 메모리초과가 나더라구요.

BFS로 할땐 각 위치에서 4방향 확인해가며 값을 ++하는 식으로 경우를 셌는데

중복방문이 많아서 큐가 폭발하는건가요? 복잡도를 계산하면 4^(N*M)라고 보는게 맞는지요?

DP코드는 어쩌다 풀긴했는데, 혹시 이러한 형태의 DP문제 있으면 추천도 부탁드립니다!

감사합니다

#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;
int R, C;
int m[501][501];
int visited[501][501];
const int di[] = { 0, 0, 1, -1 };
const int dj[] = { 1, -1, 0, 0 };
typedef pair<int, int> point;

int main(int argc, char** argv) {
	queue<point> q;
	cin >> R >> C;
	for (int i = 1; i <= R; ++i)for (int j = 1; j <= C; ++j) cin >> m[i][j];
	q.push(point(1,1));
	while (!q.empty()){
		point here = q.front(); q.pop();
		int hi = here.first; int hj = here.second;
		for (int i = 0; i < 4; ++i){
			int ni = hi + di[i];
			int nj = hj + dj[i];
			if (ni>R || ni<1 || nj>C || nj < 1)continue;
			if (m[ni][nj] < m[hi][hj]){
				visited[ni][nj]++;
				q.push(point(ni, nj));
			}
		}
	}
	cout << visited[R][C] << endl;
	return 0;
}


//////////////////////////////////////////////

#include <cstdio>
#include <iostream>
using namespace std;
int R, C;
int m[501][501];
int cache[501][501];
const int di[] = { 0, 0, 1, -1 };
const int dj[] = { 1, -1, 0, 0 };

int dy(int r, int c){
	if (r == R&&c == C)return 1;
	if (cache[r][c])return cache[r][c];
	for (int i = 0; i < 4; ++i){
		int ni = r - di[i]; int nj = c - dj[i];
		if (ni>R || ni<1 || nj>C || nj < 1)continue;
		if (m[ni][nj] < m[r][c]){
			cache[r][c] += (dy(ni, nj));
		}
	}
	return cache[r][c];
}

int main(int argc, char** argv) {
	cin >> R >> C;
	for (int i = 1; i <= R; ++i)for (int j = 1; j <= C; ++j) cin >> m[i][j];
	cout << dy(1, 1) << endl;
	return 0;
}

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

문제

문제

출처

ICPC

BFS안되는이유, 유사 Dp추천부탁드려요

ezelay 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말