백준 2644 - 촌수계산

문제

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

2644번: 촌수계산

 

풀이

 

A와 B 사이에 거리를 구하는 문제이다. 그래프 탐색인 bfs를 이용해서 A에서 B까지 거리를 구하면 된다. 만약 가는 경로가 없다면 -1을 리턴해주면 된다. bfs 탐색을 하면서 각 level이 끝날때마다 탐색 횟수를 증가시키면 된다. 탐색을 하다가 다음 방문할 정점이 B이면 탐색 횟수를 반환해준다.

 

 

코드

#include <iostream>
#include <queue>
using namespace std;
 
queue<int> q;
int A, B;
int graph[101][101];
bool visit[101];
int n;
 
int bfs(int start)
{
    visit[start] = true;
    q.push(start);
 
    bool find = false;
    int result = 0;
 
    while (!q.empty())
    {
        int len = q.size();
 
        for (int i = 0; i < len; i++)
        {
            int cur = q.front(); q.pop();
 
            for (int next = 1; next <= n; next++)
            {
                if (graph[cur][next] && !visit[next])
                {
                    q.push(next);
                    visit[next] = true;
                    if (next == B) return result + 1;
                }
            }
        }
        result++;
    }
    return -1;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> n;
 
    cin >> A >> B;
 
    int m;
    cin >> m;
 
    int x, y;
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        graph[x][y] = 1;
        graph[y][x] = 1;
    }
 
    cout << bfs(A);
 
    return 0;
}