글 읽기 - 3190 뱀 문제 런타임에러(withoutreturning)

kimgyuae 2년 전 0

어디서 WithoutReturning인지 찾아주실 분 구합니다!

자꾸 런타임 에러가 뜨네요... 반례는 질문을 통해서 다 확인했습니다.

디버깅의 경우, 스택 메모리 1MB를 초과하는 경우만 오류가 나서 스택 메모리를 128MB로 변경해서 했더니 해결됐습니다.

다 return이 제대로 있는 거 같은데 못 찾겠네요...

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#define APPLE 20
#define RIGHT 0
#define DOWN 1
#define LEFT 2
#define UP 3

using namespace std;

struct DIRECT_CONVERSION{
	int count;
	char direct[2];
};

int BOARD[100][100];
DIRECT_CONVERSION DC[100];
int N, K, L;

int play(int count, int dc_count, int direction, int x, int y, int tail_x, int tail_y) {
	cout << count<<"\n";
	/*
	cout << "x: " << x << " y: " << y << " tail_x: " << tail_x << " tail_y: " << tail_y << "\n";
	cout << "머리: " << BOARD[y][x] << " 꼬리: " << BOARD[tail_y][tail_x] << "\n";
	*/
	if (count > 10000)
		return count;

	if (direction == RIGHT) 
		++x;
	else if (direction == DOWN) 
		++y;
	else if (direction == LEFT) 
		--x;
	else if (direction == UP) 
		--y;
	
	if (dc_count < L) { //방향 변환
		if (count == DC[dc_count].count) {
			if (strcmp(DC[dc_count].direct, "L") == 0) {
				direction -= 1;
				if (direction < 0)
					direction += 4;
				direction %= 4;
			}
			else
				direction = (direction + 1) % 4;
			dc_count++;
		}
	}

	if (x < 0 || x >= N || y < 0 || y >= N) //벽에 부딪히는 경우
		return count;

	if (BOARD[y][x] >= RIGHT && BOARD[y][x] <= UP) //자기 자신에게 부딪힐 경우
		return count;

	if (BOARD[y][x] != APPLE) {
		if (BOARD[tail_y][tail_x] == RIGHT) {
			BOARD[tail_y][tail_x] = -1;
			tail_x++;
		}
		else if (BOARD[tail_y][tail_x] == DOWN){
			BOARD[tail_y][tail_x] = -1;
			tail_y++;
		}
		else if (BOARD[tail_y][tail_x] == LEFT) {
			BOARD[tail_y][tail_x] = -1;
			tail_x--;
		}
		else if (BOARD[tail_y][tail_x] == UP) {
			BOARD[tail_y][tail_x] = -1;
			tail_y--;
		}
	}
	/*cout << "이동: " << "(" << x << "," << y << ")\n";
	cout << "이동 보드" << BOARD[y][x] << "\n\n";
	*/
	BOARD[y][x] = direction;
	/*
	cout << "이동 보드" << BOARD[y][x] << "\n";
	cout << "이동 방향" << direction << "\n\n";
	*/
	play(count + 1, dc_count, direction, x, y, tail_x, tail_y);
}

int main(void) {	
	int x, y;
	int i;

	//INPUT AND INIT
	memset(BOARD, -1, sizeof(BOARD));
	scanf("%d", &N);
	scanf("%d", &K);
	for (i = 0;i < K;i++) {
		scanf("%d %d", &y, &x); //y가 행이고 보드는 [행][열]
		BOARD[y-1][x-1] = APPLE;
	}

	scanf("%d", &L);
	for (i = 0; i < L;i++) 
		scanf("%d %c", &DC[i].count, &DC[i].direct);
	BOARD[0][0] = RIGHT;
	printf("%d\n", play(1, 0, RIGHT, 0, 0, 0, 0));

	return 0;
}

kimgyuae 2년 전 0

85번째 줄이 실행된 후에는 조건에 맞춰서 count가 반환됩니다. 게임이 끝날 경우를 다 맞춰줬다고 생각해서 저렇게 코드를 마무리 했는데 혹시 게임이 끝나지 않는 반례가 있을까요?

djm03178 2년 전 1

반환되지 않습니다. 재귀 호출된 함수가 반환을 했다고 해서 자신도 반환을 하는 것은 아닙니다.

재귀 호출은 다른 함수를 호출하는 것과 다를 것이 없습니다. 예를 들어, 그 함수의 마지막 부분에 pow(1, 1);을 호출한다고 해서 pow의 반환값을 play 함수가 반환하지는 않을 것입니다. 마찬가지로 play를 재귀호출 하더라도 재귀호출된 play가 반환한 값을 자신도 그대로 반환하지는 않습니다. 이 부분은 아무것도 반환하지 않아 undefined behavior가 발생하는 부분입니다.

재귀호출된 함수가 반환한 값을 자신도 그대로 반환하려면 여타 함수를 호출할 때와 마찬가지로 return play(count + 1, dc_count, direction, x, y, tail_x, tail_y); 와 같이 return을 명시해줘야 합니다.

kimgyuae 2년 전 0

오... 알려주신 사실을 간과했네요... 알려주셔서 감사합니다! 많은 도움이 됐습니다! 사실 방금 전에 그냥 반복문으로 다시 만들어서 했더니 되서 그냥 이렇게 해야겠다하고 생각하고 있었는데 정말 감사합니다. :)

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

문제

문제

출처

ICPC

3190 뱀 문제 런타임에러(withoutreturning)

kimgyuae 2년 전 0

djm03178 2년 전 1

kimgyuae 2년 전 0

djm03178 2년 전 1

kimgyuae 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말