[SW Expert Academy] #1219 길찾기 - BFS, QUEUE

매일 DFS로만 풀었더니 BFS는 상대적으로 못하는 것 같아서... 연습이 필요했음

c++ queue 사용하고

memset 쓰려면 #include<cstring> 까먹지 말고

 

 

#include < iostream >
#include < queue >
#include < cstring > // memset
using namespace std;

const int MAX = 100;

int visited[MAX]={0,};
int data_1[MAX]={0,};
int data_2[MAX]={0,};

// BFS
int slove(){
    queue < int >  q;
    q.push(0); // add A

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        
        // find out B - 탈출조건
        if( cur == 99 ) return 1;
        
        // 방문 확인
        if( visited[cur] != 0) continue;
        else visited[cur]=1;
        
        // first node
        if(data_1[cur]!=0) q.push(data_1[cur]);
        
        // second node
        if(data_2[cur]!=0) q.push(data_2[cur]);
    }
    return 0;
}

int main(void){

    for(int tc=1; tc < = 10; tc++){
        int sz;
        
        // 입력
        cin >> tc >> sz;
        for(int i=0; i < sz; i++){
            int from, to;
            //cin >> from >> to;
            scanf("%d %d",&from,&to);
            if( data_1[from] ==0 ) data_1[from]=to;
            else data_2[from]=to;
        }
        
        int answer = slove();
        cout << '#' << tc << ' ' << answer << endl;
        
        // 초기화
        memset(visited, 0, sizeof(int)*MAX);
        memset(data_1, 0, sizeof(int)*MAX);
        memset(data_2, 0, sizeof(int)*MAX);
    }
    return 0;
}