BFS를 이용한 최단경로의 길이(C++)

n을 입력 받고 n x n크기의 1 과 0으로 이루어진 2차원 배열을 입력 받는다. 0은 지나갈 수 없는 길이고 1을 지나 갈 수 있다. (0,0)에서 출발하여 (n-1,n-1)로 가는 최단 경로의 길이를 출력하라.


BFS를 이용하여 DFS를 이용한 방법보다 더 빨리 최단 경로의 길이를 구할 수 있다.
DFS는 모든 경우를 검색해야 하는 방면, BFS는 레벨 순으로 검색하기 때문에 가장 얕은 레벨에서 목적지에 도달했을때 이 경로가 최단 경로임을 보장할 수 있기 때문이다.



#include <iostream>
#include <windows.h>
using namespace std;
int x[30],y[30],l[30];
int a[10][10],cnt,n;//지도와 새로운 데이터를 받을 위치
void push(int xx, int yy, int ll){//큐에 데이터를 받는 함수
     x[cnt]=xx;
     y[cnt]=yy;
     l[cnt]=ll;
    
     cnt++;
}
void BFS(){
     int pos;//현재 사용하는 데이터 위치
    
     y[0]=0;
     x[0]=0;
     l[0]=1;//처음 길이는 1이다.
     pos=0;//배열의 0번쨰 칸 부터 불러서 써야한다.
     cnt=1;//당연히 새로운 데이터는 1번 칸부터 채워야 한다.
    
     //목적지에 도달할때 까지 반복한다.
     while(pos<cnt&&(x[pos]!=n-1||y[pos]!=n-1)){//pos가 cnt를 따라잡거나 목적지에 도달.
                 a[y[pos]][x[pos]]=0;//재방문을 방지하기 위해
                
                 if(y[pos]>0&&a[y[pos]-1][x[pos]]==1){
                                                     push(x[pos],y[pos]-1,l[pos]+1);
                 }
                 if(x[pos]>0&&a[y[pos]][x[pos]-1]==1){
                                                     push(x[pos]-1,y[pos],l[pos]+1);
                 }
                 if(y[pos]<n-1&&a[y[pos]+1][x[pos]]==1){
                                                     push(x[pos],y[pos]+1,l[pos]+1);
                 }
                 if(x[pos]<n-1&&a[y[pos]][x[pos]+1]==1){
                                                     push(x[pos]+1,y[pos],l[pos]+1);
                 }
                
                 pos++;
     }
     if(x[pos]==n-1&&y[pos]==n-1)cout<<l[pos]<<endl;
}
                                               
int main(){
   
    int i,j;
    cin>>n;
   
    for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>a[i][j];
   
    BFS();
   
    system("PAUSE");
    return 0;
}

실핼결과

5
1 1 1 1 0
0 1 0 1 1
1 1 0 0 1
1 0 0 0 1
1 1 1 1 1
9
Press any key to continue . . .


덱을 이용하여 큐를 만들면 더욱 코드가 간결해진다.

#include <iostream>
#include <windows.h>
#include <deque>
using namespace std;
deque<int> x,y,l;
int a[10][10],n;//지도와 새로운 데이터를 받을 위치

void BFS(){
    
     x.push_back(0);
     y.push_back(0);
     l.push_back(1);
    
     //목적지에 도달할때 까지 반복한다.
     while(!x.empty()&&(x.front()!=n-1||y.front()!=n-1)){
                 a[y.front()][x.front()]=0;//재방문을 방지하기 위해
                
                 if(y.front()>0&&a[y.front()-1][x.front()]==1){
                                                     x.push_back(x.front());
                                                     y.push_back(y.front()-1);
                                                     l.push_back(l.front()+1);
                 }
                 if(x.front()>0&&a[y.front()][x.front()-1]==1){
                                                     x.push_back(x.front()-1);
                                                     y.push_back(y.front());
                                                     l.push_back(l.front()+1);
                 }
                 if(y.front()<n-1&&a[y.front()+1][x.front()]==1){
                                                     x.push_back(x.front());
                                                     y.push_back(y.front()+1);
                                                     l.push_back(l.front()+1);
                 }
                 if(x.front()<n-1&&a[y.front()][x.front()+1]==1){
                                                     x.push_back(x.front()+1);
                                                     y.push_back(y.front());
                                                     l.push_back(l.front()+1);
                 }
                
                 x.pop_front();
                 y.pop_front();
                 l.pop_front();
     }
     if(x.front()==n-1&&y.front()==n-1)cout<<l.front()<<endl;
}
                                               
int main(){
   
    int i,j;
    cin>>n;
   
    for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>a[i][j];
   
    BFS();
   
    system("PAUSE");
    return 0;
}
실행결과
5
1 1 1 1 1
0 0 1 0 1
1 1 1 0 1
1 0 0 0 1
1 1 1 1 1
9
Press any key to continue . . .

코딩하는데 소문자l을 숫자 1로 잘못 치는 바람에 한동안 컴파일에러를 봐야 했다. l자리에 1이 어쩌다 들어가기라도 하면 눈으로 봤을땐 아무 이상없는데 코드가 컴파일이 되지 않으니 꽤 해매게 된다.