[BOJ]백준 21738번: 얼음깨기 펭귄(C++)/BFS

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

21738번: 얼음깨기 펭귄

이것도 오랜만에 풀어본 BFS 문제

최근에 풀어볼 문제를 고를 때 백준 사이트에서 지원하는 대회의 문제들을 자주 보고 있다

대학 대회/유저 개최 대회 같은 경우에 최근에는 검수가 철저히 된 완성도 있는 문제들이 많아서 코테 대비하기에도 좋은 것 같당 ㅎ.ㅎ

이렇게 생긴 익숙한 그림에서 "최대 몇 개를 깰 수 있지?"라고 물어봤을 때에는 모든 얼음에 대해 깨는 경우를 구하는 시뮬레이션인줄 알았으나

이렇게 [지지대 얼음]이 루트로, [펭귄이 서있는 얼음]이 단말로 가게 다시 그렸을 때 BFS라는 것을 알았다

(문제에서 서로 다른 두 얼음을 잇는 경로는 하나뿐이라고 했고, 모든 얼음은 연결되어 있으니 사실 트리이다)

이 그림에서는 [1-10-12], [3-8-12]가 서로 다른 지지대 얼음을 연결할 수 있는 가장 짧은 경우이므로 해당 노드들을 제외한 노드를 전부 제거해주는 것이 곧 최대한 많은 얼음을 깨는 것이당

따라서 모든 지지대얼음(S 이하의 노드)에서 BFS를 수행해서 펭귄이 서있는 얼음까지의 거리를 구하고, 제일 작은 두 경로를 구하는 문제

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

int n, s, p, ans;
vector<vector<int>> g;
vector<bool> visit;

int main() {
	scanf("%d%d%d", &n, &s, &p);
	g = vector<vector<int>>(n + 1);
	priority_queue<int> pq;

	for (int i = 0, a, b; i < n - 1; i++) {
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}

	visit = vector<bool>(n + 1, false);
	for (int i = 1; i <= s; i++) {
		queue<int> q;

		q.push(i);
		visit[i] = 1;

		for (int time = 1, b = 1; b == 1; time++) {
			int size = q.size();
			while (size--) {
				int cur = q.front(); q.pop();
				if (cur == p) {
					pq.push(-time); b = 0; visit[cur] = 0;
					break;
				}

				for (auto x : g[cur]) {
					if (!visit[x]) {
						q.push(x); visit[x] = 1;
					}
				}

			}
		}
	}
	ans += -pq.top(); pq.pop();
	ans += -pq.top(); pq.pop();
	ans--;

	printf("%d", n-ans);

	return 0;
}