백준 25402: 트리와 쿼리
https://www.acmicpc.net/problem/25402 DFS?처음 내가 생각한 아이디어는 단순 DFS를 사용해서, S에 속한 정점들만, 탐색하여 사이즈를 구한 뒤에, Size * (Size - 1) / 2로 쌍의 갯수를 더하므로 답을 구하는 심플한 아이디어였다. 시간 초과가 의심되지만, 혹시나 하는 마음에 코드를 구현해보았다.#include #include using namespace std;using ll = long long;const int MAX = 250001;vector adj[MAX];ll N, Q, K, A, B, S[MAX];bool v[MAX], g[MAX];ll dfs(int here){ ll ret = 1; for (int there : adj[here]) { if ..
백준 2276: 물 채우기
https://www.acmicpc.net/problem/2276 유사한 문제이 문제를 보자마자 떠올린 문제가 있다.https://www.acmicpc.net/problem/1113 바로, "백준 1113: 수영장 만들기"이다. 이 문제는 바깥에서부터 물의 수위를 조절하며, BFS를 돌아서, 채울 수 있는 물을 구하면 된다. 다만, 이 문제는 물의 수위가 1~10 사이여서 가능하였고, 여기서 다룰 문제는 1~1,000,000,000까지의 높이를 가지므로 다른 해결책을 강구해야한다. 시도한 아이디어그래서 나는 물통의 높이들을 전부 우선순위 큐에 넣고, 높이가 작은 순서대로 순회하는 알고리즘을 떠올렸다.일단 우선순위 큐에서 높이와 위치를 꺼낸 뒤에, 위치를 기준으로 DFS를 돌며, 주위의 높이 중 가장 작은..
