[백준 24447번] 알고리즘 수업 - 너비 우선 탐색 4 (C++)

문제링크 : https://www.acmicpc.net/problem/24447

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, R, cnt = 1;
vector<int>v[100001];
ll visited[100001], seq[100001], sum=0; 

void bfs()
{
    queue<int>q;
    q.push(R);
    visited[R]=0; //시작점 (깊이)
    seq[R]=1; //방문순서 (첫번째)

    while(!q.empty())
    {
        int cur = q.front();
        seq[cur] = cnt++; //방문순서 저장
        q.pop();
        for(int i=0; i<v[cur].size(); i++)
        {
            int next = v[cur][i];
            if(visited[next]!=-1) continue; //방문불가한 경우 스킵
            visited[next] = visited[cur]+1; //깊이 증가
            q.push(next);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M >> R;
    for(int i=1; i<=M; i++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1; i<=N; i++) sort(v[i].begin(), v[i].end());
    memset(visited, -1, sizeof(visited));
    bfs();
    for(int i=1; i<=N; i++) sum += visited[i] * seq[i];
    cout << sum;
    return 0;
}

 

백준 24483번 문제의 bfs 버전 문제이다.

내용은 동일하고 단지 dfs에서 bfs로 바뀌었다.

 

참고링크 : https://blob-thinking.tistory.com/381

[백준 24483번] 알고리즘 수업 - 깊이 우선 탐색 4 (C++)