글 읽기 - dfs와 dp를 사용했다고 생각하는데 시간초과가 뜹니다

rkdgh98 4년 전 0

코드에 대해 설명드리자면

어떤 한 경로 a가 도착지점에 도달하면 도달하기 위해 거쳐왔던 경로의 path값을 각각 1씩 더해줍니다.
만약 다른 경로 b가 위 경로 a와 부딪혔을 때, 탐색을 중단하고 돌아가면서 b의 path에 부딪힌 칸의 path 값만큼 더해줍니다.
결국 path[1][1]에는 모든 path값이 더해질 것이고, 이것이 답이됩니다.

아래는 문제의 TC를 통해 만들어진 path 값들입니다.

이렇게 생각하고 풀었는데, 더이상 어떤 방법으로 시간을 줄일 수 있는 지 모르겠습니다.

도와주시면 감사드리겠습니다 !!

#include <iostream>
using namespace std;

int map[502][502];
int path[502][502];
int n,m;

int dfs(int a, int b)
{
	if(path[a][b]>0)
	{
		return path[a][b];
	}
	if(a==m&&b==n)
	{
		return 1;
	}
	for(int i=-1;i<=1;i+=2)
	{
		if(map[a][b]>map[a+i][b])
		{
			path[a][b]+=dfs(a+i,b);
		}
		if(map[a][b]>map[a][b+i])
		{
			path[a][b]+=dfs(a,b+i);
		}
	}
	return path[a][b];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin>>m>>n; //[m][n]
	for(int i=0;i<m+2;i++)
	{
		map[i][0] = map[i][n+1] = 10001;
	}
	for(int i=0;i<n+2;i++)
	{
		map[0][i] = map[m+1][i] = 10001;
	}
	for(int i=1;i<m+1;i++)
	{
		for(int j=1;j<n+1;j++)
		{
			cin>>map[i][j];
		}
	}
	dfs(1,1);
    
	cout<<path[1][1]<<'\n';
	return 0;
}

djm03178 4년 전 1

어떤 지점 (a,b)에서 끝으로 가는 길이 단 하나도 없었다고 가정해봅시다. 이 경우 path[a][b]의 최종 값은 얼마가 될까요?

또, 이 지에 대한 탐색을 이미 끝낸 후, 나중에 다른 경로를 통해 다시 이 지점을 오게 되면 어떻게 될까요?

rkdgh98 4년 전 0

@djm03178

소중한 시간 내셔서 답변 달아주심에 정말 감사드립니다!!

죄송하지만.. 말씀 이해가 잘 되지 않네요 ㅠㅠ

끝으로 가야지만 그때부터 if(a==m&&b==n) { return 1; }를 통해 path에 1이 더해지기 때문에, 끝으로 갈 수 있는 길이 아예 없다면 path[1][1]은 초기값 0으로 유지되지 않나요?

탐색을 끝낸 뒤에 나중에 다른 경로를 통해 다시 이 지점을 오게 되면, if(path[a][b]>0) { return path[a][b]; }를 통해 그 지점에 저장되어 있는 path 값을 가지고 되돌아 가도록 짠건데, 제가 제 코드를 잘못 이해하고 있는걸까요?

djm03178 4년 전 2

path[1][1]만 0인 게 아니라 path[a][b]도 0이 될 거고, 그러면 이미 path[a][b]가 계산이 끝난 상태인데도, 나중에 다시 (a,b)에 갔을 때 0이 바로 반환되는 게 아니라 다시 탐색을 들어간다는 것을 말씀드린 겁니다.

rkdgh98 4년 전 0

아!!!!!!!!!!!!!!!!!!!!!!!

그래서 시간이 더 걸리는거였군요

정말 감사드립니다 ㅠㅠ

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

문제

문제

출처

ICPC

dfs와 dp를 사용했다고 생각하는데 시간초과가 뜹니다

rkdgh98 4년 전 0

djm03178 4년 전 1

rkdgh98 4년 전 0

djm03178 4년 전 2

rkdgh98 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말