[백준OJ] 얼음깨기 펭귄

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

21738번: 얼음깨기 펭귄

---

 

-풀이-

필요한 정보는 펭귄이 있는 얼음으로부터 지지대 역할을 하는 얼음사이의 거리들이다. 

문제를 해결하기 위해서는, 펭귄이 서있는 얼음과 최소 2개의 얼음이 연결되어있어야 하며, 그 얼음또한 지지대 역할을 하는 얼음에 연결이 되어있어야한다는점, 최대개수의 얼음을 깨려면 얼음을 최소한으로 남겨야 한다는 점이다.

따라서 지지대역할을 하는 얼음~펭귄~지지대 역할을 하는 얼음까지의 개수가 최소가 되어야 한다.

 

1. 입력을 받으며 노드 사이의 관계를 연결해준다.

2. 입력받은 p를 기준으로 dfs탐색을 하며, 지지대 역할을 하는 얼음(1~S사이의 노드)을 만난경우 P부터의 깊이를 저장한 뒤 return 한다.

3. 지지대역할을 하는 얼음들의 깊이를 오름차순으로 sorting한다.

4. 펭귄이 서있는 얼음과, 펭귄이 서있는 얼음으로부터 짧은거리의 지지대역할을 하는 얼음을 순서대로 2개를 합친 개수를 전체 얼음에서 빼준다면 답이 나온다.

 

-시간복잡도-

지지대역할을 하는 얼음의 깊이를 저장하는 로직 = O(N)

정렬 = O(N Log N)

결과값 도출 = O(1)

 

-코드-

 

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
vector<int> maze[328001];
vector<int> d;
int n, s, p;
int result = 0;

void make_depth(int now, int parent, int depth) {
	if (1 <= now && now <= s) {
		d.push_back(depth);
		return;
	}

	for (int i = 0; i < maze[now].size(); i++) {
		int next = maze[now][i];
		if (next != parent) {
			make_depth(next, now, depth + 1);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> s >> p;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		maze[a].push_back(b);
		maze[b].push_back(a);
	}
	make_depth(p, -1, 0);
	sort(d.begin(), d.end());
	cout << n - d[0] - d[1] - 1;
	return 0;
}