글 읽기 - 고수님들 제발 도와주세요 ㅠㅠㅠㅠ

kysloves 6년 전 0

[코드 설명]

기본적인 BFS 알고리즘을 따르면서, 구조체에 좌표값뿐만 아니라 레벨값도 저장해서 목표 점에 도달했을시 해당 레벨값을 리턴하는 방식입니다. BFS 특성상 거리가 1인것부터,2인것부터,3인것부터... 순차적으로 탐색해나가기 때문에 최초로 목표점에 도달했을때가 무조건 최소의 칸수를 나타내는 거라고 생각했구요.

[문제 상황]

"틀렸습니다"만 계속 나오고 있습니다. 여기있는 질문이랑 인터넷 풀이 다 뒤적거리면서 혹시 배열의 크기가 부족한 것은 아닌지, 입력을 받을 때 잘못 입력받고 있는것은 아닌지 의심해보고 여러 방면으로 시도해보았으나 해결이 되지 않았습니다.

대체 어떤 채점용 테스트케이스에서 에러가 나오는걸까요?

꼭 좀 도와주십시오. 정말 너무너무 궁금합니다...ㅠㅠㅠ

#include <stdio.h>

typedef struct tagQueue{
	int x;
	int y;
	int level;
}Queue;

Queue queue[10001];

int N,M,i,j;
int Maze[101][101];
int front=0,rear=0;
int visit[101][101]={0};


int BFS(int x,int y){
	int popX,popY,popLevel,i,X,Y;
	int dx[4]={0,0,1,-1};//동서남북
	int dy[4]={1,-1,0,0};

	queue[rear].x=x;
	queue[rear].y=y;
	queue[rear].level=1;
	rear++;

	if(N==1 && M==1){ // 1*1 행렬이 입력된 경우
		return 1;
	}

	while(front<rear){
		popX=queue[front].x;
		popY=queue[front].y;
		popLevel=queue[front].level;
		front++;

		visit[popX][popY]=1;

		if(popX==N-1 && popY==M-1){
			return popLevel;
		}

		for(i=0;i<4;i++){
			X=popX+dx[i];
			Y=popY+dy[i];

			if(X>=0 && X<N && Y>=0 && Y<M){

				if(Maze[X][Y]==1 && visit[X][Y]==0){
					if((X==N-1) && (Y==M-1)){
						return popLevel+1;
					}
					queue[rear].x=X;
					queue[rear].y=Y;
					queue[rear].level=popLevel+1;
					rear++;
				}
			}
		}
	}
	return -1;
}



int main(){

	int result;

	
	scanf("%d%d",&N,&M);
	
	for(i=0;i<N;i++){
		for(j=0;j<M;j++){
			scanf("%1d",&Maze[i][j]);
		
		}
	}

	result=BFS(0,0);

	if(result>0){
		printf("%d\n",result);
	}

	return 0;
}

fresmic 6년 전 1

BFS 내의 visit 의 위치가 잘못된거 같네요..

위 소스에서 visit의 위치만 적절하게 수정해 제출하니까 통과했습니다! 참고하세요 :D

ehddml3 6년 전 2

큐에 넣을때 visit값을 체크해주는게 어떨까요? 아직 pop이 되지 않았을 때는 값이 여러번 갱신될 수 있을 것 같네용

ehddml3 6년 전 1

헛 쓰고 코드 확인해보는동안 답변이 달렸네요ㄷ

kysloves 6년 전 0

생각해보니 큐에 같은 지점이 여러번 들어갈 수 있겠네요 ㅠㅠㅠ 덧글달아주신 fresmic, ehddml3 님 정말 감사합니다! 배워갑니다!

이따 집에 가서 해결해보고 해결되면 이 글에도 "해결"태그 달겠습니다 감사해요

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

문제

문제

출처

ICPC

고수님들 제발 도와주세요 ㅠㅠㅠㅠ

kysloves 6년 전 0

fresmic 6년 전 1

ehddml3 6년 전 2

ehddml3 6년 전 1

kysloves 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말