글 읽기 - dfs, 재귀 풀이 시에 메모리가 터지지 않는 이유가 궁금합니다.

danny253 5년 전 0

M, N의 최댓값이 500

테이스 케이스를 지도의 최대 사이즈로 가정하고

dfs 재귀 호출이 가장 깊이 될수 있는 케이스는 아래 그림처럼의 경우 지도의 사이즈만큼, M*N만큼 재귀의 깊이가 될것이라고 생각합니다.

그럼 M, N의 최댓값이 500이니 250000번의 재귀 호출이 일어날수있는데

2만 5천의 깊이 라면 메모리가 터질거라고 생각했지만 그렇지않고 정답을 받아 의문이 들어 질문 남깁니다.

이정도는 터지지않는 깊이인가요? 재귀에 대한 이해가 잘못된것일수도 있어 정답받은 소스도 첨부함니다.

> 최악의 경우<

12 11 10 9

5 6 7 8

4 3 2 1

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

const int MAX_N = 501;
int M, N;
int board[MAX_N][MAX_N];
int cache[MAX_N][MAX_N];
int near[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };

bool isRange(int row, int col)
{
    return row > 0 && row <= M && col > 0 && col <= N;
}

int dfs(int row, int col)
{
    int & ret = cache[row][col];
    if(ret != -1)
        return ret;

    if(row == M && col == N)
        return ret = 1;

    ret = 0;
    for(int index = 0; index < 4; index++) {
        int nearRow = row + near[index][0];
        int nearCol = col + near[index][1];

        if(isRange(nearRow, nearCol) && board[row][col] > board[nearRow][nearCol])
            ret += dfs(nearRow, nearCol);
    }

    return ret;
}

int main(void)
{
    cin >> M >> N;

    memset((void*)cache, -1, sizeof(cache));
    for(int i = 1; i < M+1; i++)
        for(int j = 1; j < N+1; j++)
            cin >> board[i][j];

    cout << dfs(1, 1) << '\n';
    return 0;
}

sait2000 5년 전 2

높이가 10000이하니까 최대 약 10000번까지니까 문재 없지 않을까요?

danny253 5년 전 0

높이가 10000이하라는 조건이 있었군요! 감사합니다.

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

문제

문제

출처

ICPC

dfs, 재귀 풀이 시에 메모리가 터지지 않는 이유가 궁금합니다.

danny253 5년 전 0

sait2000 5년 전 2

danny253 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말