글 읽기 - c++로 구현해봤는데 어디가 틀렸는지 모르겠어요.

rygsa123 5년 전 0

함수 이름은 BFS 인데 사실 제가 BFS를 잘 모르거든요.

문제에 BFS라고 나와서 함수 이름만 그렇게 정해놨고 사실 BFS랑은 상관없습니다.

큐를 사용하여 구현하라고 하던데 저는 그 사실을 모르고 문제를 풀어서 알고리즘 자체는 상당히 조잡합니다.

만, 2178번 문제에 나와있는 예제는 이상없이 출력되고, 10x10의 임의의 map을 입력해도 제가 해본 선에서는 아무 문제 없이 답을 출력하더군요.

그런데 제출하면 틀렸다고 합니다.

어떤 반례가 있는건지... 잘 상상이 안가네요.

고수분들 제 코딩 좀 보시고 답 좀 부탁드려요.

visit[i][j]의 다음 이동 가능한 지점에 visit[i][j] +1 을 대입해가면서 이동합니다.

예를 들면

map[][]

1 0 1 1 1 1

1 0 1 0 1 0

1 0 1 0 1 1

1 1 1 0 1 1

visit[][]
1 0 9 10 11 12
2 0 8 0 12 0
3 0 7 0 13 14
4 5 6 0 14 15

알고리즘이 무척 지저분한 코드이지만.. 부탁드립니다. ㅠㅠ

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

int count;
int front,rear;
int map[100][100];  //입력받는 map
int visit[100][100];  //지점에 대한 방문 정보를 저장하는 배열


int BSF(int N, int M)
{
	visit[0][N-1] = 1;   //시작 지점을 방문
	front++;      //while구문을 돌리기 위한 변수 (큐랑 상관없음 ㅠ)
	
	while(front > rear)  //문제 조건 때문에 필요 없을 듯 했지만 끝 지점에 도달 못하는 경우도 고려해봄
	{
		for(int j=N-1;j>=0;j--)   //N-1행이 제일 윗행 이고 0행 까지 내려갑니다.
		{
			if( visit[M-1][0]) break;   //우측하단의 끝 지점에 도착하면 break
			for(int i=0;i<M;i++)   // 0열에서 M-1열 까지
			{				
				if( visit[M-1][0] ) break;//우측하단의 끝 지점에 도착하면 break
				if( visit[i][j])
				{
                    //visit[i][j]에 방문된 기록이 있으면 상하좌우 각각 map이 존재하는지 && 방문을 안했는지 검사합니다.
                    //조건이 맞으면 그전에 방문한 visit[i][j]의 값에 +1을 하여 그 다음 지점에 값을 대입해줌
					if( map[i+1][j]==1 && visit[i+1][j]==0 ) { visit[i+1][j] = visit[i][j]+1;  front++; }
					if( map[i][j+1]==1 && visit[i][j+1]==0 ) { visit[i][j+1] = visit[i][j]+1;  front++; }
					if( map[i-1][j]==1 && visit[i-1][j]==0 ) { visit[i-1][j] = visit[i][j]+1;  front++; }
					if( map[i][j-1]==1 && visit[i][j-1]==0 ) { visit[i][j-1] = visit[i][j]+1;  front++; }
					if( visit[M-1][0] ) break;//우측하단의 끝 지점에 도착하면 break
					
				}
				if( visit[M-1][0]) break;//우측하단의 끝 지점에 도착하면 break
			}
		
		}
		rear++;
	}
	return visit[M-1][0];  //우측하단 끝 지점의 visit 배열 값 출력
}

int main()
{
	int N,M;
	cin>>N>>M;
	
	string in;
    
	for(int j=N-1;j>=0;j--)  //입력
	{
		cin>>in;
		 for(int i=0;i<in.length();i++)
			 if(in[i]=='1') map[i][j]=1; 
	}	
		
	cout<<BSF(N,M)<<endl;
	
}

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