[알고리즘 문제] 백준2644 - 촌수계산

www.acmicpc.net/problem/2644

2644번: 촌수계산

bfs로 문제를 해결할 수 있으며 시작점을 기준으로 그래프에서 연결되어 있는 노드를 이동하면서 노드의 위치가 도착지점이면 그때의 dis값을 출력하도록 합니다. 그래프에서 이동한 노드는 다시 방문하면 안되기 때문에 이 부분은 check[]로 관리하였습니다.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int n, start, des, m;
    cin >> n >> start >> des >> m;
    int graph[101][101];

    int n1, n2;
    for (int i = 0; i < m; i++)
    {
        cin >> n1 >> n2;
        graph[n1][n2] = 1;
        graph[n2][n1] = 1;
    }

    queue<pair<int, int>> que;
    int visited[101];

    que.push({start, 0});
    visited[start] = 1; // start 노드는 방문했음을 체크

    while (!que.empty())
    {
        int cur = que.front().first;
        int dis = que.front().second;
        que.pop();

        if (cur == des) // 현재 위치가 도착지점이면 dis를 출력하고 종료
        {
            cout << dis << endl;
            return 0;
        }

        for (int i = 1; i <= n; i++) // 방문하지 않은 노드를 탐색
        {
            if (graph[cur][i] && !visited[i]) // 그래프에서 연결되어 있고 아직 방문하지 않은 노드이면
            {
                que.push({i, dis + 1});
                visited[i] = 1;
            }
        }
    }

    cout << -1 << endl;
    return 0;
}