글 읽기 - 두 소스의 차이점이 궁금합니다.

djfls0304 4년 전 0

위의 코드는 1,1 에서 M,N까지 순차적으로 경로를dp에 저장하여 dp[M][N] 까지 도착 가능한 경로를 구한것이고
아래의 코드는 dfs 를 사용하여 구한것 입니다.

두 코드의 시간 차이가 많이 나지 않는다고 생각하는데

어떤 부분 두 코드에서 시간차이가 나오는지 궁금합니다.

#include <stdio.h>
int arr[501][501];
int dp[501][501];
int M, N;
int cnt;
int A[4] = { 1, 0, -1, 0 };
int B[4] = { 0, 1, 0, -1 };
int fun(int a,int b)
{
	if (a == M && b == N) return;
	for (int i = 0; i < 4; i++)
	{
		int nexta = a + A[i];
		int nextb = b + B[i]; //상하좌우 모두 이동가능하므로.
		if (arr[nexta][nextb]<arr[a][b])
			if (arr[nexta][nextb] != 0)
			{
				dp[nexta][nextb] += 1;
				fun(nexta, nextb);
			}
	}
	return;
}
int main()
{
	scanf("%d %d", &M, &N);
	for (int i = 1; i <= M; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			scanf("%d", &arr[i][j]);
		}
	}
	fun(1,1);
	printf("%d", dp[M][N]);
}
//sol
#include <stdio.h>
int arr[501][501];
int dp[501][501];
int M, N;
int a[4] = { 1, 0, -1, 0 };
int b[4] = { 0, 1, 0, -1 };
int dfs(int x, int y)
{
	if (dp[x][y] != -1) return dp[x][y]; //값이 이미 있는경우 또계산하지말고 있는값 리턴
	if (x <= 0 || x > M || y <= 0 || y > N) return 0; //범위 벗어난 경우는 불가능하므로 0리턴
	if (x == 1 && y == 1) return 1; //기저사례

	dp[x][y] = 0;
	for (int i = 0; i < 4; i++)
	{
		int nextX = x + a[i];
		int nextY = y + b[i]; //상하좌우 모두 이동가능하므로.

		if (arr[nextX][nextY]>arr[x][y])
			dp[x][y] += dfs(nextX, nextY);
	}
	return dp[x][y];
}

int main()
{
	scanf("%d %d", &M, &N);
	for (int i = 1; i <= M; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			scanf("%d", &arr[i][j]);
		}
	}
	memset(dp, -1, sizeof(dp));
	printf("%d", dfs(M, N));

}

seico75 4년 전 0

윗 소스가 시간 초과가 날 것 같습니다.

아래는

if (dp[x][y] != -1) return dp[x][y];

와 같이 dp 를 써서 중복 계산을 막지만 웟 소스는 전혀 그런 로직이 없네요.

사실 윗소스는 마지막 dp 값 외에는 참조도 하지 않아서 dp 배열 대신에 하나의 변수가 있어도 충분한 해법이네요

마지막 점까지 가는 경우수를 그냥 다 세는 방법이고, 역시 dfs 로 보이구요.

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

문제

문제

출처

ICPC

두 소스의 차이점이 궁금합니다.

djfls0304 4년 전 0

seico75 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말