2644번 촌수계산

쉬운 문제였다.

전형적인 BFS 문제이다.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int n = 0, m = 0;
 
int sv = 0, ev = 0;
 
vector<vector<int> > v;
 
bool visit[101] = { false, };
 
queue<int> q;
 
int BFS(int start)
{
    q.push(start);
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int here = q.front();
 
            q.pop();
 
            if (here == ev)
            {
                return ret;
            }
 
            if (visit[here]) continue;
 
            visit[here] = true;
 
            for (int next : v[here])
            {
                if (!visit[next])
                {
                    q.push(next);
                }
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
int main(void)
{
    scanf("%d", &n);
 
    v.resize(n + 1);
 
    scanf("%d %d", &sv, &ev);
 
    scanf("%d", &m);
 
    int left = 0, right = 0;
 
    while (m--)
    {
        scanf("%d %d", &left, &right);
 
        v[left].push_back(right);
        v[right].push_back(left);
    }
 
    printf("%d\n", BFS(sv));
 
    return 0;
}