[BaekJoon/백준] 2644번 촌수계산

 

이 문제는 딱 BFS의 대표적인 유형이다!!

 

 

주의할 점은, 촌수가 없을 경우 0이 아닌 -1을 출력해 주어야 한다.

#include <iostream>
#include <queue>
#include <vector>


using namespace std;

vector<int> v[101];
bool visit[101];
int depth[101];

int N;

int START, END;

int M;


void bfs(int start) {
    
    queue<int> que;
    que.push(start);
    visit[start] = true;
    
    
    while(!que.empty()) {
        
        int x = que.front();
        
        que.pop();
        
        for(int i = 0; i < v[x].size(); i++) {
            
            int xx = v[x][i];
            
            if(!visit[xx]) {
                
                que.push(xx);
                visit[xx] = true;
                
                depth[xx] = depth[x] + 1;
                
                if(xx == END) // 굳이 더 이상 할 필요 없음.
                    return;
            }
            
            
        }
        
    }
    
}


int main() {
    
    int A, B;
    
    cin >> N;
    
    cin >> START >> END;
    
    cin >> M;
    
    for(int i = 0; i < M; i++) {
        
        cin >> A >> B;
        
        
        v[B].push_back(A);
        v[A].push_back(B);

        
    }
    
    bfs(START);
    
    cout << ((depth[END] == 0) ? -1 : depth[END]) << "\n";
    
}

처음에 모지리하게 단방향으로 생각했었다가,, 양방향으로 해야 함을 알았다.

 

 

소요시간 : 15분