[ boj : 21738 ] 얼음깨기 펭귄

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

21738번: 얼음깨기 펭귄

문제 : 팽귄이 물에 안빠지도록 하기까지 깨트릴수 있는 최대 얼음의 개수를 구하시오

해설 : "이때, 지지대가 연결되어 있다는 것은 지지대로부터 서로 다른 일반 얼음들을 통해 연결 관계가 이어져 있는 것을 이야기한다" 라는 문구를 잘 생각해보면, 지지대는 다른 지지대와 펭귄이 있는 위치를 제외하고는 연결이 되지 않는다는 것을 알 수 있습니다.

따라서 그냥 각 지지대까지의 depth를 구한다음에 정렬하여 2개를 선택해서 총 얼음의 개수에서 빼주면 됩니다.

#include<bits/stdc++.h>

using namespace std;

const int SIZE = 328010;
int pos[SIZE],visit[SIZE];
vector<int> adj[SIZE];
vector<int> dist;

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

	int n, p, s;
	cin >> n >> s >> p;
	int x, y;
	for (int i = 0; i < n-1; i++) {
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
		if(i<s) pos[i + 1] = 1;
	}
	int sum = 0, cnt = 0, check = 0;
	queue<int> q;
	q.push(p);
	visit[p] = 1;
	while (!q.empty())
	{
		cnt++;
		int size = q.size();
		for (int time = 0; time < size; time++) {
			int cur = q.front();
			q.pop();

			for (int i = 0; i < adj[cur].size(); i++) {
				if (!visit[adj[cur][i]]) {
					if (pos[adj[cur][i]] == 1) 
						dist.push_back(cnt);					
					visit[adj[cur][i]] = 1;
					q.push(adj[cur][i]);
				}
			}
		}
	}		
	sort(dist.begin(), dist.end());
	cout << n - dist[0] - dist[1] - 1;
	return 0;
}