글 읽기 - 1937(욕심쟁이 판다) 런타임에러 질문 드립니다..

ljh9032a 6년 전 0

런타임 에러 뜨는거 답변 부탁드리겠습니다.

Dfs로 중복 제거를 위해 dp에 저장 한 것을 구현하였는데 런타임 에러가 뜨네요..

이해가 안되는데 설명 좀 부탁드리겠습니다!!

#include<cstdio>
#include<vector>
#define SIZE 501

using namespace std;

int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};
int n;
vector<vector<int> > map(SIZE, vector<int>(SIZE, 0));
vector<vector<int> > dp(SIZE, vector<int>(SIZE, 0));

//범위 확인
int inRange(int y, int x)
{
	if(1 <= y && y <= n && 1 <= x && x <= n ) return 1;
	else return 0;
}

//Dfs 함수
void Dfs(int y, int x, int cnt)
{
	dp[y][x] = cnt;

	int ty, tx;
	for(int i=0; i<4; ++i){
		ty = y + dy[i];	tx = x + dx[i];
		if(map[y][x] < map[ty][tx] && inRange(ty, tx) && dp[y][x] < cnt + 1)
			Dfs(ty, tx, cnt + 1);
	}	
}

int main(void)
{
    //입력
	scanf("%d", &n);
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			scanf("%d", &map[i][j]);
		}
	}
    
    //dp를 통한 Dfs;
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			if(dp[i][j] > 0) continue;
			Dfs(i, j, 1);
		}
	}

	int answer = 0;

    //가장 큰 dp값 찾기
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			if(answer < dp[i][j]) answer = dp[i][j];
		}
	}	
	printf("%d", answer);
	return 0;
}

enochjung 6년 전 1

if(map[y][x] < map[ty][tx] && inRange(ty, tx) && dp[y][x] < cnt + 1)

dfs 함수에서 범위확인 함수를 나중에 실행했네요

ljh9032a 6년 전 0

고쳤는데 시간초과가 나네요..ㅎㅎ

혹시 inRange 함수를 if(inRange(ty, tx) && map[y][x] < map[ty][tx] && dp[y][x] < cnt + 1) 이렇게 고쳤는데

위에것이랑 무슨 큰 차이가 있는건가요??

enochjung 6년 전 1

n=500이면 가끔가다 ty나 tx가 501이 되는데요

if(map[y][x] < map[ty][tx] && inRange(ty, tx) ... 이면

map[ty][tx]에서 map[501][...]라는 선언하지 않은 곳을 참조해서 런타임에러가 뜨고요

if(inRange(ty, tx) && map[y][x] < map[ty][tx] ... 의 경우에는

inRange(ty, tx)가 거짓이 되어, 뒤의 밑줄 친 부분을 검사하지도 않고 조건문을 탈출하기 때문에 map[501][...] 부분에 접근하지 않게 됩니당

ljh9032a 6년 전 0

정말 감사합니다 ..ㅎㅎ

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

문제

문제

출처

ICPC

1937(욕심쟁이 판다) 런타임에러 질문 드립니다..

ljh9032a 6년 전 0

enochjung 6년 전 1

ljh9032a 6년 전 0

enochjung 6년 전 1

ljh9032a 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말