[c++/알고리즘] 그래프 최단거리 - BFS

그래프 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 구한다.
-> 가중치는 모두 같고, 최소 이동 간선수를 구하는 문제이니 BFS를 사용한다.

#include <iostream>
#include <vector>
#include <queue>
// 1번에서 정점으로 가는 최소 이동 간선수

using namespace std;

int n, m, a, b, dis[20], ch[20], x;
vector<int> graph[20];
queue<int> Q;

int main(){

    cin >>n >> m;
    // 그래프 그리기
    for(int i=0; i<m; i++){
        cin >> a >> b;
        graph[a].push_back(b);
    }
	
    // 1번 정점부터 출발
    Q.push(1);
    ch[1] = 1;

    while(!Q.empty()){
    	
        x = Q.front();
        Q.pop();
        // x에 연결된 정점 queue에 넣기.
        for(int i=0; i<graph[x].size(); i++){
            if(ch[graph[x][i]] == 0){
                ch[graph[x][i]] = 1;
                Q.push(graph[x][i]);
                // 정점에서 [x][i]까지의 거리는 이전 정점 x에서 1을 더한 값이다.
                dis[graph[x][i]] = dis[x]+1;
            }
        }
    }

    for(int i=2; i<=n; i++){
        cout << i << " : " << dis[i] << endl;
    }

}