글 읽기 - dp 재귀 호출 방문 체크 질문

lmcoa15 5년 전 0

문제를 푼 방법은 도착 지점에 이르렀을 때 1을 리턴하는 방식으로 풀었습니다.

메모이제이션으로 리턴하도록 풀었는데 이전에 방문하였는지를 체크하는 방법을 다르게 했더니 하나는 fail이 떠서 질문 올립니다.

우선 아래의 코드는 통과한 코드고 dfs 부분만 봐주시면 됩니다.

통과한 코드는 visit체크를 일단 dfs를 무조건 탄 다음에 검사해서 방문했으면 dp값을 리턴했습니다.

그런데 visit체크를 새로운 dfs로 타기 직전에 검사하고 방문한 적이 없으면 for문 안에서 검사했더니 오류가 떴습니다.

물론 도착 지점인 dp[N-1][N-1]에 미리 1을 세팅해서 도착지점을 방문했을 때 1을 리턴할 수 있도록 main에서 따로 설정했습니다.

무슨 차이가 있어서 visit체크를 for문에서 하면 오류가 뜨는지 궁금합니다.

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<vector<int>> map;
vector<vector<long>> dp;
vector<vector<int>> visited;

int dy[2]={1,0};
int dx[2]={0,1};

//통과
long dfs(int y,int x){
    
    if(y==N-1 && x==N-1)
        return 1;
    
    if(visited[y][x])
        return dp[y][x];
    
    visited[y][x]++;
    for(int i=0;i<2;i++){
        int ny=y+dy[i]*map[y][x];
        int nx=x+dx[i]*map[y][x];
        
        if(ny>=N || nx>=N)
            continue;
        
        dp[y][x]+=dfs(ny,nx);
    }
    
    return dp[y][x];
}
int main(){
    
    cin>>N;
    
    map=vector<vector<int>> (N,vector<int>(N,0));
    dp=vector<vector<long>> (N,vector<long>(N,0));
    visited=vector<vector<int>> (N,vector<int>(N,0));

    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            scanf("%d",&map[i][j]);
    
    
    cout<<dfs(0,0)<<endl;
    
    return 0;
}



//통과x
long dfs(int y,int x){
    
    for(int i=0;i<2;i++){
        int ny=y+dy[i]*map[y][x];
        int nx=x+dx[i]*map[y][x];
        
        if(ny>=N || nx>=N)
            continue;
        
        if(visited[ny][nx])
            return dp[ny][nx];
        
        visited[ny][nx]++;
        dp[y][x]+=dfs(ny,nx);
    }
    
    return dp[y][x];
}
int main(){
    
    cin>>N;
    
    map=vector<vector<int>> (N,vector<int>(N,0));
    dp=vector<vector<long>> (N,vector<long>(N,0));
    visited=vector<vector<int>> (N,vector<int>(N,0));

    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            scanf("%d",&map[i][j]);
    
    dp[N-1][N-1]=1;
    cout<<dfs(0,0)<<endl;
    
    return 0;
}

wreckitralph 3년 전 0

1 1 1

위 예제를 입력하였을때 dp의 값과 visited에 방문한 순서를 출력해보았습니다.

(dp)

2 0 0
2 0 0
1 1 1

(vistied에 방문 순서 기록)

0 6 0
1 5 0
2 3 4

dfs(1,1)에서 (ny,ny)가 (2,1)이 될때 visited가 true이므로 return dp(2,1)하지만 이는

dp[1][1]에 더해지지 않고 dfs(1,1)에서 return 1시키게 되어 dp[1][0]에 더해집니다.

dfs(1,2)로 넘어가지도 못하고 return 1 로 종료하게 됩니다.

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

문제

문제

출처

ICPC

dp 재귀 호출 방문 체크 질문

lmcoa15 5년 전 0

wreckitralph 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말