2533번 사회망 서비스 (SNS)
<문제 설명>
<알고리즘 유형>
다이내믹 프로그래밍을 트리와 접목시킨 알고리즘 유형으로 다이나믹 프로그래밍에 약한 나에게 매우 어려웠던 문제.
항상 제대로된 점화식이 생각이 나지 않는다.. 조건 찾는 것도 보면 막상 쉬운데 혼자 생각할 때는 왜이렇게 갈피를 못잡는지.. 이 문제 또한 그러했다.
<문제 풀이>
우선 다이내믹 프로그래밍을 사용해야 하는 만큼 조건과 점화식을 잘 세워야 한다.
친구관계가 트리형태로 존재하고 그 중 최소 얼리 어답터를 찾는 것인데, 나는 저 그래프 그림만 보고 '아 깊이를 번갈아가면서 해당 노드들이 모두 얼리어답터라면 다른 노드들도 커버할 수 있구나? 그러면 깊이가 홀수인 노드들의 수를 구하고, 나머지 노드들의 수와 비교했을 때 더 작은 값이 정답이겠구나' 싶은 생각이 들었고 BFS를 이용하여 코드를 구현하였지만 실패하였다.
이유는 이런 경우의 수도 존재하기 때문이었다. 즉 문제를 풀기 위해 제대로 된 조건은
1. 부모노드가 얼리 어답터 라면 자식 노드는 얼리 어답터 일수도, 아닐 수도 있다.
2. 부모노드가 얼리 어답터가 아니라면 자식 노드는 반드시 얼리 어답터여야 한다.
라는 조건을 가진다. 따라서
DP[i][0] //자신이 얼리 어답터가 아닐 경우
DP[i][1] //자신이 얼리 어답터일 경우.
DP[부모노드][0] += DP[자식노드][1]
DP[부모노드][1] += min(DP[자식노드][0], DP[자식노드][1])
이라는 점화식을 갖는다.
이와 재귀를 이용해서 코드를 구현한다.
<코드 구현>
#include <iostream>
#include <vector>
#define MAX 1000001
using namespace std;
int N;
vector<bool> visited;
vector<int>* graph;
vector<int>* dp;
void getEarlyAdaptor(int idx) {
int vertex;
visited[idx] = true;
dp[idx].push_back(0);
dp[idx].push_back(1);
for (int i = 0; i < graph[idx].size(); ++i) {
vertex = graph[idx][i];
if (visited[vertex]) continue;
getEarlyAdaptor(vertex);
dp[idx][0] += dp[vertex][1];
dp[idx][1] += min(dp[vertex][0], dp[vertex][1]);
}
}
int main() {
graph = new vector<int>[MAX];
dp = new vector<int>[MAX];
int u,v;
int result;
cin >> N;
visited = vector<bool>(N+1, false);
for (int i = 0; i < N-1; ++i) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
getEarlyAdaptor(1);
result = min(dp[1][0], dp[1][1]);
cout << result << endl;
}
<잘못 구상한 조건으로 잘못된 코드 구현>
#include <iostream>
#include <vector>
#include <queue>
#define MAX 1000001
using namespace std;
int N;
vector<bool> visited;
vector<int> height;
int computeEarlyAdaptor(vector<int>* graph, int n) {
int result=1;
int vertex;
queue<int> q;
q.push(n);
visited[n] = true;
height[n]++;
while (!q.empty()) {
vertex = q.front();
for (int i = 0; i < graph[vertex].size(); ++i) {
int node = graph[vertex][i];
if (visited[node]) continue;
q.push(node);
visited[node] = true;
height[node] = height[vertex] + 1;
if (height[node] % 2) result++;
}
q.pop();
}
return result;
}
int main() {
vector<int>* graph = new vector<int>[MAX];
int u,v;
int result;
cin >> N;
visited = vector<bool>(N+1, false);
height = vector<int>(N+1, 0);
for (int i = 0; i < N-1; ++i) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
result = computeEarlyAdaptor(graph, 1);
result = result > N - result ? N - result : result;
cout << result;
}
참고
https://comyoung.tistory.com/41