글 읽기 - 큐 크기에 따른 출력변화

pinoco3 2년 전 0

우선 문제는 해결하였으나 출력이 왜 그렇게 됐는지 이해가 되지않아 질문드립니다.

메모리를 적게 이용하기 위하여

큐를 1001로 하여 rear와 front가 1001이 됐을 때 0이 되도록 코드를 작성하였습니다.

하지만 입력을 하기와 같이 입력했을 때

1000000 1000000 1 1 2

출력이 500500 으로 나와

배열크기를 10001로 변경하여 테스트를 하니

출력이 50050으로 나오게 됐습니다.

배열크기에 따라 출력이 변하는 이유와 메모리를 적게 사용면서 큐를 구현하려면 어떻게 해야하는지 궁금합니다.

#include<stdio.h>
int visit[1000001]={0,};
int F,S,G,U,D;
int cnt=0,out=0;
int front=0,rear=0,rf=0,rear_flag=0;
int queue[10001]={0,}; //큐 배열
int bfs(int s,int g){
	int n;
	visit[s]=1;
	queue[rear]=s;
	rear++;
	rf=rear;
	while(front<=rear||rear_flag==1){
		n=queue[front];
		front++;
		if(front>10000){ //큐 크기 넘어가면 앞으로 이동
			front=0;
			rear_flag=0;
		}
		if(n==g){
			out=1;
			break;
		}
		if(n+U<=F&&visit[n+U]==0){
			visit[n+U]=1;
			queue[rear]=n+U;
			rear++;
			if(rear>10000){ //큐 크기 넘어가면 앞으로 이동
				rear=0;
				rear_flag=1;
			}
		}
		if(n-D>0&&visit[n-D]==0){
			visit[n-D]=1;
			queue[rear]=n-D;
			rear++;
			if(rear>10000){ //큐 크기 넘어가면 앞으로 이동
				rear_flag=1;
				rear=0;
			}
		}
		if(rf<=front){
			cnt++;
			rf=rear;
		}
	}
	return 0;
}
int main(){
	scanf("%d %d %d %d %d",&F,&S,&G,&U,&D);
	if(S==G){
		printf("0");
	}
	else if(S<G&&U==0){
		printf("use the stairs");
	}
	else if(S>G&&D==0){
		printf("use the stairs");
	}
	else{
		bfs(S,G);
		if(out==1){
			printf("%d",cnt);
		}
		else{
			printf("use the stairs");
		}
	}
	return 0;
}

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

문제

문제

출처

ICPC

큐 크기에 따른 출력변화

pinoco3 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말