문제 참 길다
풀이 과정 🔎
해석해 보기 🤔
a. 하나의 노드를 (얼리 어답터가 아닌 사람으로) 선택했을 때, 해당 노드와 인접한 모든 노드는 무조건 얼리 어답터가 되어야 한다.
b. (a)의 조건을 만족하면서 최대한 많은 노드를 선택했을 때, 선택되지 않은 노드의 수가 정답이다.
c. 최대한 적은 노드를 얼리 어답터로 선택해서 모든 간선에 대해 간선이 하나 이상의 얼리 어답터 노드를 갖게 한다.
풀이 구상하기
-
처음에는 단순하게 접근해서, 트리에서 level 0 - level 2 - level 4...를 선택하는 경우나, level 1 - level 3 - level 5...를 선택하는 경우를 비교하면 되지 않을까 생각했다. (= 임의의 노드로부터 거리를 구했을 때 짝수인 노드들 / 홀수인 노드들로 구분. 어떤 노드를 루트로 선택하든 결과는 같다.)
그러나 예제에서 서로 인접한 노드를 둘 다 얼리 어답터로 했을 때 해가 나오는 경우가 있어서 기각. -
(c)로부터 출발해서, 간선이 '연결하는 두 정점 중 하나 이상이 얼리 어답터' 라는 조건을 만족하는지를 저장하고, 우선순위 큐를 사용해 조건을 만족하지 않는 간선과 가장 많이 연결되어 있는 노드를 하나씩 얼리 어답터로 빼는 방식도 생각했다.
이 방식은 가능할 것 같아서 구현도 하고 예제까지는 통과했는데 제출했더니 틀렸다 🥲 아마 다음 두 부분이 문제가 됐지 않을까 의심스럽다...
- 조건을 만족하는 간선이 변경됐을 때, 우선순위 큐에 들어가 있는 가중치를 바로 업데이트하지 못하고 일단 우선순위 큐에서 노드를 하나 꺼내서 가중치를 수정 > 다음 노드와 비교해가며 가중치가 가장 높은 노드를 찾는 방식으로 구현했다.
- 가중치가 같은 노드가 있을 때 우선순위 판단을 할 기준이 없다.
- 결과적으로 dp 태그를 보고 나서 정답 로직을 구상할 수 있었다 😂
- dp로 접근하니 각 노드가 '얼리 어답터일 때'와 '얼리 어답터가 아닐 때' 필요한 최소 비용 (= 얼리 어답터의 수)를 각각 저장하고 활용하는 방식이 떠올랐다.
- 노드가 얼리 어답터라면?
인접한 각각의 노드는 무엇이든 상관 없으므로 최소값을 사용- 노드가 얼리 어답터가 아니라면?
인접한 각각의 노드는 모두 얼리 어답터여야 하므로 해당 값을 사용
- 특정 노드에서 이렇게 비용을 구하려면 인접한 노드의 비용이 모두 구해진 상태여야 하므로, 트리의 리프 노드부터 출발해서 서브 트리 범위에서 비용을 구하고, 자식 노드의 비용이 모두 구해진 노드를 다음 순서로 처리했다.
- 이렇게 루트까지 반복하면 루트 노드가 얼리 어답터일 경우 / 아닐 경우의 비용이 구해지므로 해당 값 중 더 작은 값이 정답이다.
트리에서의 dp를 아직 많이 풀어 보지 않아서 dp로 접근할 생각을 바로 하지 못한 게 조금 아쉬웠던 문제.
정답 코드 ✅
// C++ 사용
#include <iostream>
#include <vector>
#include <queue>
#define pnt pair<int, int>
#define MAX 1000001
using namespace std;
// 간선 정보 저장
vector <int> v[MAX];
// 리프 노드부터 시작하는 처리 순서를 구하기 위해, 각 노드의 부모 노드와 자식 노드의 개수 저장
int parents[MAX] = {0, }, children[MAX] = {0, };
// 각 노드에서 얼리 어답터일 때, 아닐 때 비용 저장
int dp[MAX][2] = {0, };
int main() {
ios_base::sync_with_stdio(false);
int n;
cin>>n;
// 간선 정보를 입력 받는다
int x, y;
for(int i = 1; i < n; i++) {
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
// 부모-자식 정보를 저장하기 위해 1번 노드를 루트로 정하고 트리 탐색
queue <int> q, leaf;
int cur;
q.push(1);
while(!q.empty()) {
cur = q.front();
q.pop();
children[cur] = v[cur].size() - (cur == 1 ? 0 : 1);
// 자식이 없을 경우 리프 노드이므로 큐에 저장
if(children[cur] == 0) {
leaf.push(cur);
}
for(int i = 0; i < v[cur].size(); i++) {
if(v[cur][i] != parents[cur]) {
q.push(v[cur][i]);
parents[v[cur][i]] = cur;
}
}
}
// 모든 자식의 비용 계산이 끝난 노드를 차례로 순회하며 자신의 비용을 부모에 추가
int parent;
while(!leaf.empty()) {
cur = leaf.front();
parent = parents[cur];
leaf.pop();
// cur이 얼리 어답터인 경우 자기 자신도 세어야 한다
dp[cur][1]++;
if(cur == 1) {
// 루트 노드는 부모에 업데이트할 필요 x, 종료
break;
}
// parent가 얼리 어답터가 아닐 경우, cur은 무조건 얼리 어답터여야 한다
dp[parent][0] += dp[cur][1];
// parent가 얼리 어답터일 경우, cur은 무엇이든 무관하므로 최솟값을 사용한다
dp[parent][1] += (dp[cur][1] < dp[cur][0] ? dp[cur][1] : dp[cur][0]);
// 부모에게 계산이 남아 있는 자식 노드가 줄어든다
// 계산해야 할 자식 노드가 더이상 없다면 해당 노드도 큐에 추가한다
if(--children[parent] == 0) {
leaf.push(parent);
}
}
// 루트 노드가 얼리 어답터인 경우, 아닐 경우를 비교
cout<<(dp[1][0] < dp[1][1] ? dp[1][0] : dp[1][1])<<'\n';
return 0;
}