인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ 이 메모리 초과는 재귀함수를 많이 호출해서 생기는 초과에요.

메모리초과가 뜰 때는 배열을 많이 선언했나.

또는

재귀함수가 많이 호출되는 것은 아닌가를 중점적으로 디버깅을 하시는게 좋습니다.

원래 SAM님의 코드는 다음과 같은데요. 뭐가 문제일까요?

아 참고로 visited 부분은 q w = 0이렇게 되어있길래 고쳤습니다 :)

	for(int i=0;i<4;i++){
		y=q+dy[i];
		x=w+dx[i];
		if(y < 0 || x < 0 || y >=n || x >= m) continue;
		if(!visited[y][x]&&arr[y][x]!='T'){
			visited[y][x] = visited[q][w]+1;
			sum+=dfs(y,x); 
			visited[y][x] = 0; 
		}	
	}

바로 y, x를 전역변수로 선언한게 문제입니다.

지역변수와 전역변수의 차이를 좀 생각해볼까요?

지역변수는 스택에 위치하며 다른 함수의 인스턴스에 영향을 주지도, 받지도 않습니다.

교안의 있는 설명은 다음과 같습니다.

Stack은 지역변수, 매개변수, 실행되는 함수에 의해 늘어나거나 줄어드는 메모리 영역입니다. 함수가 호출될 때마다 호출될 때의 환경 등 특정 정보가 stack에 계속해서 저장됩니다. 

또한, 재귀함수가 호출된다고 했을 때 새로운 스택 프레임이 매번 사용되기 때문에 함수 내의 변수 집합이 해당 함수의 다른 인스턴스 변수를 방해하지 않습니다.

자, 그렇다면 여기서 y, x는 dfs라는 재귀함수를 통해 변하게 되겠죠?

y, x = 1 >> dfs() >> dfs() >> y, x = 3

이런식이 될 겁니다.

근데 여기서

dfs 밑에 visited = 0이렇게 되어있는데요.

나는 y, x = 1에 해당하는 visited를 0으로 바꾸고 싶은데도 불구하고

y, x = 3이 0으로 바꿔지게 되는 것이죠.

전역변수를 적절히 쓰되 이런식으로 매개변수로 넘겨야 할 것은 전역변수로 쓰지 않는 것이 좋습니다.

제가 sam님의 코드를 기반으로 수정좀 해봤는데요. 참고 부탁드립니다.

http://boj.kr/c88eb7e6ed044d9ca494e30bef0ebeb0

그리고 담부터 질문하실 때 코드 들여쓰기 좀 부탁드립니다.

sam님은 질문을 많이 하시는 것도 열심히 하는것도 너무나 좋지만, 코드 디버깅하는 입장에서 들여쓰기 안된 코드 보는 것은 정말 힘듭니다..

또 질문 있으시면 언제든지 질문 부탁드립니다.

감사합니다.

강사 큰돌 올림.