취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24447번 문제인 알고리즘 수업 - 너비 우선 탐색 4이다.
문제는 아래 링크를 확인하자.

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

24444번 문제(링크)와 24446번 문제(링크)를 섞은 문제이다.

방문 순서와 노드의 깊이(루트와의 거리)를 계산하면서 문제의 값을 구성하는 항의 값들을 노드의 방문 순서대로 구해 문제를 해결하자.

방문을 할 수 없는 노드의 경우 방문 순서를 0으로 정의하였으므로 해당 노드는 문제의 답에 영향을 주지 않음을 관찰하자.

문제의 답이 32비트 정수 자료형으로 표현할 수 있는 범위를 넘을 수 있음에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;

int N, M, R;
vector<int> G[100001];
ll dist[100001];
ll turn;

ll ans;

void bfs() {
	queue<int> que;
	que.push(R);
	dist[R] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		ans += ++turn * (dist[cur] - 1);
		for (auto& nxt : G[cur]) {
			if (dist[nxt]) continue;
			dist[nxt] = dist[cur] + 1;
			que.push(nxt);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> R;
	while (M--) {
		int u, v; cin >> u >> v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}

	for (int i = 1; i <= N; i++) sort(G[i].begin(), G[i].end());

	bfs();

	cout << ans;
}