[코드업] 4039 : 놀이공원 (C)

출처 : 2011 교원프로그래밍경진대회

 

알고리즘 : BFS

 

풀이

조건 하나가 더 추가된 BFS 문제이다. 재귀함수로 풀려고 하면 DFS가 되어 버리니 조심해야한다.

특정 위치에서 상하좌우를 확인해야 하므로 dir(방향배열)을 통해 간단하게 처리했다.

BFS의 장점은 가장 먼저 목표에 도달한 시행에서의 값이 답이 된다는 것이다.

따라서 목표에 도달했을 때 반복문을 탈출하여 출력하면 된다.

 

#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
 
int in[1002][1002];
int dir[4][2]={{0,1}, {0,-1}, {1,0}, {-1,0}};
int check[1002][1002];
 
 
typedef struct dot{
    int a,b,ans;
}dot;
 
queue<dot> q;
 
 
int main(){
    int ans=9999999;
    int n,m, flag=0;
 
    cin>>n>>m;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>in[i][j];
        }
    }
    
    check[1][1]=1;
    dot first={1,1,1};
    q.push(first);
 
    while(!q.empty()){
 
        int a=q.front().a,b=q.front().b,tmp=q.front().ans; 
        q.pop();
            
        if(a==n&&b==m){
            ans=tmp;
            break;
        }
            
            
        for(int i=0;i<4;i++){
        
            int na=a+dir[i][0],nb=b+dir[i][1];
        
            if( check[na][nb] || !in[na][nb] || abs(in[na][nb]-in[a][b])>1 )
                continue;
            
            dot temp={na,nb,tmp+1};
            q.push(temp);
            check[na][nb]=1;
        }
        
        
    }
    if(ans!=9999999)
        cout<<ans;
    else
        cout<<"0";
}