글 읽기 - 재귀함수에 대한 질문이 있습니다.

karlin 4년 전 0

아래 두 코드의 로직이 똑같다고 생각했는데 막상 실행해보니 결과가 다르게 나와서 질문드립니다.

예를 들어서

3 3

1 -9 -9

-9 1 -9

-9 1 1

을 대입하면 , 정답 코드는 5를 리턴하는 반면 틀린 코드는 -5를 반환합니다.

틀린코드와 정답코드의 차이점은

틀린코드는 현재까지의 합을 함수의 인자로 받고 목적지에 도착하면 그 값을 반환하고

정답코드는 함수 내에서 map[y][x]에 왼쪽, 오른쪽, 아래쪽으로 갔을 때 중 최댓값을 더한 후 그 값을 반환하는 것입니다.

틀린코드가 정답코드와 다른 결과값을 리턴하는 이유가 뭘까요?ㅠㅠ

// 틀린 코드
#include <iostream>

using namespace std;

int n,m;
int map[1001][1001];
bool visited[1001][1001];
int dp[1001][1001][3];

int solve(int y, int x, int dir, int s){
    if(y==n && x==m) return s; // 틀린 코드에선 목적지에 도착했을 때 s를 리턴함
                               // 반면 정답 코드에선 map[n][m]를 리턴함
    
    int& ans = dp[y][x][dir];
    
    if(ans != -987654321) return ans;
    int left, right, down;
    left=right=down=-987654321;

    
    visited[y][x] = true;
    if(y>=1 && y<=n && x-1>=1 && x-1<=m && !visited[y][x-1]) left = solve(y, x-1, 0, s+map[y][x-1]);
    if(y>=1 && y<=n && x+1>=1 && x+1<=m && !visited[y][x+1]) right = solve(y, x+1, 1, s+map[y][x+1]);
    if(y+1>=1 && y+1<=n && x>=1 && x<=m && !visited[y+1][x]) down = solve(y+1, x, 2, s+map[y+1][x]);
    visited[y][x] = false;
    
    ans = max(left, max(right, down)); // 틀린 코드에선 왼쪽, 오른쪽, 아래쪽 값 중 최댓값을 **대입함**
                                       // 반면 정답 코드에선 map[y][x]에 왼쪽, 오른쪽 ,아래쪽 값 중 최댓값을 **더함**
    
    return ans;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>map[i][j];
            dp[i][j][0] = -987654321;
            dp[i][j][1] = -987654321;
            dp[i][j][2] = -987654321;
        }
    }
    cout<<solve(1,1,0,map[1][1])<<endl;
    
    return 0;
}

// 정답인 코드
#include <iostream>

using namespace std;

int n,m;
int map[1001][1001];
bool visited[1001][1001];
int dp[1001][1001][3];

int solve(int y, int x, int dir){
    if(y==n && x==m) {
        return map[y][x];// 틀린 코드에선 목적지에 도착했을 때 s를 리턴함
                         // 반면 정답 코드에선 map[y][x]를 리턴함
    }
    
    int& cur = dp[y][x][dir];
    if(cur!=-987654321) return cur;
    
    int left, right, down;
    left=right=down=-987654321;

    
    visited[y][x] = true;
    if(y>=1 && y<=n && x-1>=1 && x-1<=m && !visited[y][x-1]) left = solve(y, x-1, 0);
    if(y>=1 && y<=n && x+1>=1 && x+1<=m && !visited[y][x+1]) right = solve(y, x+1, 1);
    if(y+1>=1 && y+1<=n && x>=1 && x<=m && !visited[y+1][x]) down = solve(y+1, x, 2);
    visited[y][x] = false;
    
    cur = map[y][x]+max(down, max(left, right));// 틀린 코드에선 왼쪽, 오른쪽, 아래쪽 값 중 최댓값을 **대입함**
                                                // 반면 정답 코드에선 map[y][x]에 왼쪽, 오른쪽 ,아래쪽 값 중 최댓값을 **더함**
    
    return cur;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>map[i][j];
            dp[i][j][0] = -987654321;
            dp[i][j][1] = -987654321;
            dp[i][j][2] = -987654321;
        }
    }
    cout<<solve(1,1,0)<<endl;
    return 0;
}

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

문제

문제

출처

ICPC

재귀함수에 대한 질문이 있습니다.

karlin 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말