글 읽기 - 1937번 BFS로 접근했는데 런타임 에러가 나옵니다

juhongkim2 7년 전 0

배열범위를 벗어난것 같지도 않고 무한루프를 도는것 같지도 않은데 런타임에러가 뜹니다

어디서 잘못된건지 좀 알려주세요ㅠㅠ

#include <stdio.h>

int map[501][501];
int n;

typedef struct{
	int xpos,ypos,cnt;
}Point;

Point queue[501*501];

int IsinRange(int x, int y)
{
	if(x<0 || y<0 || x>=n || y>=n)
		return 0;

	return 1;
}

int main()
{
	int i,j,k,f,r,x,y,c,tx,ty,max=0,result=0;
	int dx[4]={0,1,0,-1};
	int dy[4]={-1,0,1,0};

	scanf("%d",&n);

	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			scanf("%d",&map[i][j]);
		}
	}
	
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			f=-1,r=-1;
			queue[++r].xpos=j;
			queue[r].ypos=i;
			queue[r].cnt=1;

			while(f!=r){
				x=queue[++f].xpos;
				y=queue[f].ypos;
				c=queue[f].cnt;

				for(k=0;k<4;k++){
					tx=x+dx[k];
					ty=y+dy[k];

					if(IsinRange(tx,ty) && map[ty][tx]>map[y][x]){
						queue[++r].xpos=tx;
						queue[r].ypos=ty;
						queue[r].cnt=c+1;
					}
				}
			}

			if(max<c)
				max=c;
		}
	}

	printf("%d\n",max);

	return 0;
}

portableangel 7년 전 2

큐에 들어가는 원소의 개수가 최대 501*501개를 넘을 수가 있네요.
예를 들어 2*2 맵이
1 2
2 3
과 같이 생겼고, 맨 왼쪽 위의 칸(1,1) 에서 출발한다면
queue에 (1,1)을 push하고 시작 -> queue에 (1,2), (2,1)이 push됨 -> (1,2), (2,1) 각각에서 (2,2)를 push
도합 5개의 원소가 들어갑니다.

어떤 칸에 방문할 수 있는 경우의 수가 2회 이상이라면(위 예제에서의 2,2처럼), 해당 칸에서 방문할 수 있는 칸들도 모두 2번씩 방문될테고

이것이 누적되면 큐의 사이즈를 넘어가게 됩니다.

위 BFS의 아이디어를 이용해 '어떤 칸에 방문했을 때, 그 칸에서 시작하는 최장 경로의 길이' 를 담을 501*501 배열을 이용하여
DP를 하나 설계해 보세요

nisroeld99 7년 전 1

메모이제이션 공부해보고 풀어보세요 !

juhongkim2 7년 전 0

답변정말 감사합니다!

501*501짜리 배열로 dp사용했더니 ac나오네요

그런데 그럼 이 문제는 애초에 bfs로는 풀수가 없는 문제인가요?

nisroeld99 7년 전 0

네 n =500이라 안될것같습니다

런타임에러 자체도 메모리 에러같네요 bfs에서 너무 많은 데이터를 queue에 넣은듯싶습니다.

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

문제

문제

출처

ICPC

1937번 BFS로 접근했는데 런타임 에러가 나옵니다

juhongkim2 7년 전 0

portableangel 7년 전 2

nisroeld99 7년 전 1

juhongkim2 7년 전 0

nisroeld99 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말