16173 : 점프왕 쩰리 - 재귀함수

오랜만에 실버 문제를 풀었다. 매번 브론즈로 별 찍기 정도의 난이도 문제를 풀다가 이건 좀 아닌 것 같다 싶어서 오늘은 실버 도전.

 

머릿속으로 대충.. 오른쪽이동, 아래쪽이동 함수 만들고

배열과 시작지점을 인수로 받아서 출발하면 되겠다고 생각했다. 디테일한 건 짜면서 생각하기로 했다.

 

<코드>

#include <stdio.h>
#define MMS 3 // Map Max Size

int Play(int arr[][3], int i, int j);
int goRight(int arr[][3], int i, int j);
int goDown(int arr[][3], int i, int j);

int N; // MapSize (2~3)
int END = 0;

int main() {
	int arr[MMS][MMS] = {};

	scanf_s("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf_s("%d", &arr[i][j]);
		}
	}

	Play(arr, 0, 0); // 시작 지점 설정. arr[0][0]
	if (END == 1)
		printf("HaruHaru");
	else
		printf("Hing");
	
	return 0;
}

int Play(int arr[][3], int i, int j) {
	// printf("\nPlay(%d,%d)\n", i, j); // 확인용
	if (i == N - 1 && j == N - 1) {
		END = 1;
		return 0;
	}
	goRight(arr, i, j);
	goDown(arr, i, j);
}

int goRight(int arr[][3], int i, int j) {
	int move = j + arr[i][j];
	// printf("오른쪽 : move = %d. arr[%d][%d] = %d\n", move, i, j, arr[i][j]); // 확인용
	if (move >= N || arr[i][j] == 0) // 해당 칸 수가 0이면 이동 불가.
		return 0;
	Play(arr, i, move);
}

int goDown(int arr[][3], int i, int j) {
	int move = i + arr[i][j];
	// printf("아래 : move = %d. arr[%d][%d] = %d\n", move, i,j,arr[i][j]); // 확인용
	if (move >= N || arr[i][j]==0) // 오른쪽으로 이동한 좌표가 범위를 넘어선 경우
		return 0; // 함수 종료 (아랫쪽으로 이동하는 함수가 실행됨). return 0을 주기 위해 함수반환을 void에서 int로 바꿨다.
	Play(arr, move, j);
}

 

이렇게 짰다. Play 함수에 배열과 시작좌표를 인자로 넣는다. 일단 오른쪽으로 먼저 가고, 더 이상 갈 수 없으면(move>=N) 아래로 이동하는 방식이다.

 

근데 출력이 완벽해서 제출했더니 '메모리 초과'라고 뜨는거다.

이해가 안 갔다. 맵(배열) 사이즈는 겨우 2x2에서 3x3인데 뭐가 넘치는거지??

 

질문게시판을 보니, 재귀함수가 무한루프를 돌 경우 메모리 초과가 뜬다고 했다. 아하.

다른 반례를 입력해보니 원인을 알았다. 어떤 칸에 0이 들어가 있을 경우, 오른쪽으로 아래로 계속 이동한다고 생각하지만 좌표는 전혀 바뀌지 않기(오른쪽으로든 아래로든 +0)에 무한루프를 도는 것이었다.

 

그래서 if (move >= N || arr[i][j]==0)로 함수 종료 조건에 추가 코드를 작성했더니 성공했다. 야호~