글 읽기 - dfs 시간초과

jakehsj 7년 전 0

dfs로 푸신분 있나요ㅠㅠ 시간초과 나는데.....

#include <stdio.h>
int a[100][100];
int n;
long long dfs(int x,int y)
{
    if(x==n-1&&y==n-1) return 1;
    int ret=0;
    if(a[x][y]!=0)
    {
        if(x+a[x][y]<n)
            ret+=dfs(x+a[x][y],y);
        if(y+a[x][y]<n)
            ret+=dfs(x,y+a[x][y]);
    }
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&a[i][j]);
    printf("%lld",dfs(0,0));
}

ainch96 7년 전 0

방문했던 곳을 체크하는 2차원 배열을 만들어 주셔야 합니다. 만약 저렇게 하면 중복되는 수많은 경로를 여러번 들려서 시간 초과가 발생할 수 밖에 없습니다.

jakehsj 7년 전 0

감사합니다 그런데 고쳐서 제출해봤더니 81프로에서 틀리던데 그건 왜 그런 건가요?

#include <stdio.h>
int a[100][100];
int n;
long long visit[100][100];
long long dfs(int x,int y)
{
    if(visit[x][y]!=0)
        return visit[x][y];
    if(x==n-1&&y==n-1) return 1;
    int ret=0;
    if(a[x][y]!=0)
    {
        if(x+a[x][y]<n)
            ret+=dfs(x+a[x][y],y);
        if(y+a[x][y]<n)
            ret+=dfs(x,y+a[x][y]);
    }
    visit[x][y]=ret;
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&a[i][j]);
    printf("%lld",dfs(0,0));
}

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

문제

문제

출처

ICPC

dfs 시간초과

jakehsj 7년 전 0

ainch96 7년 전 0

jakehsj 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말