글 읽기 - 재귀 호출 이해가 안되네요 질문드립니다

lswoo3021 5년 전 0

게시판에 있던 다른분 코드를 같이보려고 가져왔는데요 ..

일반적인 dfs 완전탐색에서 재귀호출은 이해가 됩니다.

종료조건을 주면.. 보통 전역변수의 값을 바꾸고 리턴하게되잖아요 ?

근데 아래와 같은 코드 22번째라인처럼 temp += dfs();는 어떤 효과를 가져오게 되는지 와닿지가 않습니다

temp 변수가 여러번 더해지는 것은 아니고, 결국 마지막에 리턴된 상수값을 더하게 되는거죠 ??

하... 어렵넹요

혹시 11번라인 부터 28번 라인... 설명이 가능하신 분 있다면 한 수만 부탁드리겠습니다 ㅠㅡㅠ

알고리즘 공부는 넘 힘드네요 ... 심화된 문제는 스스로 이해를 못하면

따로 물어볼 선생님도없고 강의도 기초적인것뿐이라서요 ㅠㅠ

재귀함수 이해하기 쉬운 방법좀 알려주세요

보통 재귀함수 이해하기가 쉽고 직관적이나, 스택오버플로가 날 수 있다 이렇게 말하는데 ...

저는 반대에요 .... 끝까지 들어갓다가 하나씩 리턴되어지는 과정이 머리속에서 너무 헷갈리네요...

백트래킹까진 이해돼서 잘풀지만.. dp 와 엮이는건 이해가 ㅠ

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

int bamboo[500][500];
int Dp[500][500];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int n, day = 1;

int dfs(int y, int x)
{
	if(Dp[y][x] != -1) Dp[y][x];
	Dp[y][x] = 1;
	for(int i = 0; i<4; i++)
	{
		int next_x = x + dx[i];
		int next_y = y + dy[i];
		if(next_x >= 0 && next_x < n && next_y >= 0 && next_y < n && (bamboo[y][x] < bamboo[next_y][next_x]))
		{
			int temp = 1;
			temp += dfs(next_y, next_x);
			Dp[y][x] = max(Dp[y][x], temp);			
			if(Dp[y][x] > day) day = Dp[y][x];

		}
	}
	return Dp[y][x];
}

int main(void)
{
	cin>>n;
	for(int i = 0; i<n; i++){
		for(int j = 0; j<n; j++){
			cin>>bamboo[i][j];
			Dp[i][j] = -1;
		}
	}

	//Dp[i][j]를 계산하기위해서 dfs(i,j) 호출
	for(int i = 0; i<n; i++){
		for(int j = 0; j<n; j++){
			if(Dp[i][j] == -1)
				dfs(i,j);
		}
	}
	/*
	for(int i = 0; i<n; i++){
		for(int j = 0; j<n; j++){
				cout<<Dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	cout<<day<<endl;
	return 0;
}

lswoo3021 5년 전 0

@djm03178 혹시 ㅠㅡㅠ 시간이 되신다면 부탁드리겠습니다 선생님 ...

lovinix 5년 전 1

일단 dfs(y,x)함수가 (y,x) 위치에서 살 수 있는 최대 일수임을 아신다면

22번째 temp에는 "for문이 돌때마다 (next_y, next_x)위치에서 살 수 있는 최대일수"가 저장됨을 알 수 있습니다.

따라서 23번째 줄은 현재위치 y,x의 위,아래,왼쪽,오른쪽에서 살 수 있는 최대 일수 중 가장 큰 값+1을 dp[y][x]에 저장하는것입니다.

lswoo3021 5년 전 1

@lovinix 감사합니다!!!

ㅠㅡㅠ 먼가 대충은 그런가 하는데...

함수가 재귀호출로 문어발식이라 .. 확실하게 이해가 안되네요 ... 더 공부해야겠어요 ..

- 19번 라인의 if문은, 현재지점에서 다음지점으로 오름차순인 순서를 기준으로 한다는 의미인거겟죠 ?

- 22번 라인에서... temp= 1; temp += dfs(next_y, next_x); 를 해주는 것은...

현재지점거리 1 + (nx, ny)의 최대일수 ? 가 되는건가요 ..? 즉... 오름차순을 만족하는 경우면 우선

계속 진행(먹방)가능한 지점이니까 더해주는거구요.

lswoo3021 5년 전 0

@lovinix 사실 제일 이해 안되는 부분이 .. dfs 가 리턴되는 부분을 보면

정확한 값이 아니라... 계속 dfs()를 돌려막기로 호출하고 그걸 더하는건데...

결국dp배열은 1이라는 값부터 시작해서 더해지는거잖아요 ?

근데 이게 재귀적으로 계속 돌려막기니까 ... 구체적으로 어떤방식으로 순환호출돼서

1, 2, 3, 이렇게 증가해서 채워져나가는지 잘 모르겠어요 ...

재귀의 시작과 끝의 리턴값을 잘 모르겠는 느낌이랄까 ..

lovinix 5년 전 1

오름차순.. 이라는게 무엇을 말씀하시는지 잘 모르겠습니다.

19번째 if문은 next_x,next_y가 N*N 배열을 벗어나지않으면서 && 다음에 움직일 곳이 지금 있는 곳보다 대나무가 많을 때 를 의미합니다.

"dfs"가 언제 끝나는가는 이 문제에서 " 더 이상 판다가 이동할 수 없는 조건 " 과 일치합니다.

즉, 사방(위,아래,왼쪽,오른쪽)에 존재하는 대나무의 수가 현재 칸에 존재하는 대나무의 수보다 "모두" 적어야합니다.

이 코드에서는 해당 조건을 만족할시, for문이 4번 도는동안(즉, 사방을 모두 검색하는동안) if문 내의 bamboo[y][x] < bamboo[next_y][next_x] 가 항상 false가 되며,

이 때 1을 dp배열의 해당위치에 저장 후, return하게됩니다. (14, 28번째 줄) (재귀의 끝)

따라서 이 위치의 옆에서 해당 위치에 접근하려 할 경우, 해당위치의 dfs함수값 + "1(현재위치)"를 하면서 값을 쌓아나가는 것입니다.

이것이 이해가 잘 안가신다면, 1차원배열 {1,3,2}로 dfs(0,0)을 실행했을 때 어떻게 진행이 될 것인가 손으로 실행과정을 적어보시는 것도 괜찮을 것 같습니다.

lswoo3021 5년 전 0

@lovinix 도움되네요 ㅠㅡㅠㅡㅠ 성심 답변감사드립니다!! 조언해주신대로 해봐야겟어요 ㅎㅎ

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

문제

문제

출처

ICPC

재귀 호출 이해가 안되네요 질문드립니다

lswoo3021 5년 전 0

lswoo3021 5년 전 0

lovinix 5년 전 1

lswoo3021 5년 전 1

lswoo3021 5년 전 0

lovinix 5년 전 1

lswoo3021 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말