[BOJ 24447] 알고리즘 수업 - 너비 우선 탐색 4 C++

난이도: Silver 2
번호: 24447
생성일: March 4, 2023 3:00 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색
언어: C++

24447번: 알고리즘 수업 - 너비 우선 탐색 4

C++

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, R, sq = 1; // N: 정점의 수, M: 간선의 수, R: 시작 정점
vector<int> path[100001]; // 인접 리스트
vector<long long> depth; // 노드의 깊이
vector<long long> seq; // 노드의 방문 순서

void BFS(int R)
{
    queue<int> Q;
    Q.push(R); // 시작 정점을 큐에 삽입
    depth[R] = 0; // 시작 정점의 깊이는 0
    seq[R] = sq++; // 시작 정점의 방문 순서는 1

    while (!Q.empty())
    {
        int cur = Q.front();
        Q.pop();
        for (int &k : path[cur]) // cur의 인접 노드들을 모두 방문
        {
            if (depth[k] != -1) // 이미 방문한 노드라면 건너뛰기
                continue;
            seq[k] = sq++; // 방문 순서 갱신
            depth[k] = depth[cur] + 1; // 깊이 갱신
            Q.push(k); // 인접 노드를 큐에 삽입
        }
    }

    long long res = 0;
    for (int i = 1; i <= N; i++)
        res += (long long)(seq[i] * depth[i]); // di * ti 값을 더해줌
    cout << res;
}

int main(void)
{
    cin.tie(0)->ios::sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> M >> R;
    depth.resize(N + 1, -1); // 깊이 배열 초기화
    seq.resize(N + 1, 0); // 방문 순서 배열 초기화

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        path[a].push_back(b); // 양방향 간선 추가
        path[b].push_back(a);
    }
    for (int i = 1; i <= N; i++)
        sort(path[i].begin(), path[i].end()); // 인접 리스트 정렬

    BFS(R); // 너비 우선 탐색 수행
}