이번 문제는 백준의 골드 3 문제 사회망 서비스이다.
문제를 한 번 차근차근 읽어보자.
최대 1,000,000개의 정점이 주어진다.
단, 사이클이 없음이 보장되며 트리의 형태임이 보장된다.
사회망 서비스 내에서, 얼리어답터가 자신의 친구라면 아이디어를 전파받는다.
즉, 친구의 친구가 얼리어답터라고 해서 아이디어를 전파받을 수는 없다.
모든 친구들이 아이디어를 전파받게 하도록 하고 싶다.
이 때, 필요한 최소 얼리어답터의 수를 구하여라!
문제를 어떻게 풀어야 할까?
문제 분석
우선, 얼리어답터 개념에 대해서 잠깐 생각해보자.
인접한 모든 노드에 대해서 아이디어를 전파할 수 있는 노드를 의미한다.
다시 말하면, 모든 노드를 방문할 수 있는 최소 노드 수를 의미할 것이다.
어떤 노드를 얼리어답터로 지정해야 모든 노드를 방문할 수 있을까?
이를 계산하기 위해서는 우리는 트리를 순회할 수 있어야 한다.
BFS? DFS? 둘 중 어떤 방식을 사용해서 순회해야 할까?
나는 위상 정렬의 개념이 가장 먼저 떠올랐다.
즉, BFS를 한번 이용해보도록 하겠다.
위상 정렬(BFS)
위상 정렬은 작업의 우선 순위를 정하는 경우에 사용된다.
보통은 진입 차수가 0인 정점부터 시작해, 순차적으로 간선을 제거하는 방식이다.
나는 반대로 진출 차수가 0인 정점부터 시작해보려고 한다.
진출 차수가 0인 정점은 바로 Leaf 노드를 의미하게 된다.
아래와 같은 개념으로 접근해보려고 코드를 짰다.
각 서브트리에 대해서, 루트를 향하며 노드의 수를 더해가는 것이다.
1번 서브트리를 예로 들면, 4 노드만 있으면 7 8 9를 방문할 수 있다.
즉, 1개의 얼리어답터로 1번 서브트리가 완성되는 것이다.
동적 계획법과 유사한 원리라고 볼 수 있다.
2번 서브트리는 1번 서브트리까지 1개의 노드가 필요했으니,
2번 서브트리를 모두 방문하려면 4, 2를 반드시 거쳐야한다는 말이다.
반복해서, 전체 트리를 모두 방문하려면 2, 3, 4 3개의 노드를 거쳐야하는 것이다.
하지만 이 개념은 틀렸다.
아래의 트리를 한번 보도록 하자.
직관적으로 이 트리에 필요한 얼리어답터는 5명이라고 볼 수 있다.
하지만 내가 계산한 방식대로라면, 8명이 필요하게 되어버린다.
내가 생각한 방식은, 깊이가 4 이상인 트리부터 통하지 않는 것이다.
원하는 대로 코드는 구현했지만, 접근 방식을 바꿔야할 것 같다.
위상정렬 포기
굉장히 오랜 고민 끝에 위상정렬은 포기하게 되었다.
고민 끝에 아래와 같이 코드가 복잡해지게 되었는데, 이는 좋지 않은 코드이다.
우선 배열을 너무 많이 선언하여, 메모리에 굉장한 부담이 되는 것이 가장 크다.
또한, 로직이 굉장히 복잡해져버려 코드의 가독성이 떨어졌다.
그리고 간과하고 있던 가장 중요한 사실.
위상정렬은 방향성이 있는 그래프에만 사용할 수 있다.
#define pib pair<int, bool>
int vertex = 0, from = 0, to = 0, early_adopter = 0;
vector<int> graph[1000001];
int outdegree[1000001];
int indegree[1000001];
int early_adopter_info[1000001]; // 메모리 초과 위험
bool visit[1000001];
void topology_sort() {
queue<pib> topology_q;
for (int i = 1; i <= vertex; i++)
if (outdegree[i] == 1 && indegree[i] == 0) {
visit[i] = true;
topology_q.push({ i, false }); // 정점, 깊이
// 진출차수가 1, 진입차수가 0인 Leaf node 부터 탐색
// true : 얼리어답터, false : 아님
}
while (!topology_q.empty()) {
int curr_node = topology_q.front().first;
bool curr_state = topology_q.front().second;
topology_q.pop();
if (early_adopter_info[curr_node])
early_adopter++;
for (int i = 0; i < graph[curr_node].size(); i++) {
int next_node = graph[curr_node][i];
if (!visit[next_node]) {
indegree[next_node]--; // 진출차수 감소, 간선의 제거를 의미
if (!curr_state)
early_adopter_info[next_node]++;
bool next_state = early_adopter_info[next_node];
cout << next_node << " " << early_adopter_info[next_node] << " " << curr_node << " " << curr_state << '\n';
// 내가 얼리어답터가 아니면?
// 부모는 무조건 얼리어답터여야 함
if (indegree[next_node] == 0) {
topology_q.push({ next_node, next_state });
visit[next_node] = true;
}
}
}
}
}
int main(){
cin >> vertex;
for (int i = 0; i < vertex - 1; i++) {
cin >> from >> to;
graph[to].push_back(from);
graph[from].push_back(to);
// 반드시 양방향으로 연결이 되어있어야 함
outdegree[from]++;
indegree[to]++;
}
topology_sort();
cout << early_adopter;
return 0;
}DFS + DP
결국 다른 사람의 풀이를 참고하게 되었다.
이 문제는 DFS와 DP를 결합했을 때 가장 간단하게 풀 수 있다고 한다.
최종적으로 아래와 같이 구현할 수 있다.
int vertex = 0, from = 0, to = 0, early_adopter = 0;
vector<int> graph[1000001];
int dp[1000001][2];
bool visit[1000001];
void dfs(int curr_node) {
visit[curr_node] = true;
dp[curr_node][1] = 1;
// 루트 노드부터 내려가는데, 루트는 반드시 어답터
for (int i = 0; i < graph[curr_node].size(); i++) {
int next_node = graph[curr_node][i];
if (!visit[next_node]) {
dfs(next_node);
dp[curr_node][0] += dp[next_node][1];
dp[curr_node][1] += min(dp[next_node][0], dp[next_node][1]);
}
}
}
int main(){
cin >> vertex;
for (int i = 0; i < vertex - 1; i++) {
cin >> from >> to;
graph[to].push_back(from);
graph[from].push_back(to);
}
dfs(1);
cout << min(dp[1][0], dp[1][1]);
return 0;
}원리는 2차원 DP 배열을 상황에 맞게 채우는 것이다.
DP[node][0]은 현재 노드가 얼리어답터가 아닌 경우를 의미한다.
DP[node][1]은 현재 노드가 얼리어답터임을 의미한다.
가장 먼저, Root 노드가 얼리어답터일 때를 가정, 1을 넣는다.
이후 DFS를 통해 Leaf 노드까지 쭉 내려간다.
Leaf 노드에 도착했다면, 이제 값을 갱신하며 위로 올라가도록 하자.
만약 현재 노드가 얼리어답터가 아니라면?
자식 노드가 얼리어답터라는 의미가 되므로, 값을 그냥 이어받는다.
하지만 현재 노드가 얼리어답터라면?
자식 노드는 얼리어답터일 수도 아닐수도 있게 된다.
따라서, 자식 노드가 얼리어답터인 쪽과 아닌 쪽에 대해 작은 값을 이어받는다.
이렇게 Root 노드까지 최소값을 갱신해온다면? 답을 찾을 수 있다!
솔직히 아이디어를 떠올리기 정말 어려운 문제였다.
1번 정점을 Root로 지정할 수 있다는 점, 2차원 DP라는 점.
시험이었다면 절대 풀지 못했을 것이다.