[BOJ 25760 // C++] 귀경길 교통상황을 알려드립니다

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

 

이번에 볼 문제는 백준 25760번 문제인 귀경길 교통상황을 알려드립니다이다.
문제는 아래 링크를 확인하자.

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

25760번: 귀경길 교통상황을 알려드립니다

N개의 지점과 N-1개의 양방향 도로, 그리고 임의의 서로 다른 두 지점이 서로 연결되어있다는 조건에서 주어진 도로망은 트리형태임을 알 수 있다.

 

차가 막히는 일이 존재하지 않을 경우 각 차량들이 톨게이트를 통과하는 데에 걸리는 시간을 미리 계산해두고, 톨게이트에서 차를 한대씩 순서대로 보내주면서 시간을 계산하는 것으로 문제를 해결하자.

 

위의 설명이 잘 이해가 되지 않는다면, 다음과 같은 더욱 단순한 형태의 문제에 대해 먼저 생각해보는 것도 좋다:

1초에 1리터의 물을 배수할 수 있는 수조가 있다. 1초부터 N초까지 각 초 Ti마다 Ki리터의 물을 이 수조에 부을 때, 이 수조에 부은 물이 전부 배수되는 시점을 구하시오.

 

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N;
vector<int> G[200001];
bool iscar[200001];
priority_queue<int> pq;

void dfs(int cur, int par, int dist) {
	if (iscar[cur]) pq.push(dist);
	dist--;
	for (auto& node : G[cur]) {
		if (node == par) continue;
		dfs(node, cur, dist);
	}
}

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

	cin >> N;
	for (int i = 1; i < N; i++) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y), G[y].emplace_back(x);
	}

	for (int i = 1; i <= N; i++) cin >> iscar[i];

	dfs(1, -1, -1);

	int ans = 0;
	while (!pq.empty()) {
		int cur = -pq.top(); pq.pop();
		if (ans < cur) ans = cur;
		else ans++;
	}

	cout << ans;
}