[KOI] 1999년 중등부 1번 촌수계산

https://www.acmicpc.net/problem/2644

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define MAX_N 100
 
int N, M, start, finish;
bool adj_matrix[MAX_N+1][MAX_N+1]; //MAX_N이 100이므로 인접행렬로 해결 가능
 
int solve() {
    queue<int> q;
    vector<bool> visited(N+1, false);
    vector<int> dist(N+1, -1);
    
    q.push(start);
    visited[start] = true;
    dist[start] = 0;
    
    while(!q.empty()) {
        int i = q.front(); q.pop();
        
        if(i == finish) return dist[i];
        
        for(int j=1; j<=N; j++) {
            if(adj_matrix[i][j] && !visited[j]) {
                q.push(j);
                visited[j] = true;
                dist[j] = dist[i] + 1;
            } 
        }
    }
    return -1;
}
 
int main() {
    scanf("%d %d %d %d", &N, &start, &finish, &M);
        
    for(int m=0; m<M; m++) {
        int i, j; scanf("%d %d", &i, &j);
        adj_matrix[i][j] = adj_matrix[j][i] = true; //undirected graph
    }
    
    int r = solve();
    printf("%d", r);
    return 0;
}