반응형
https://www.acmicpc.net/problem/2533
2533번: 사회망 서비스(SNS)
첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에
www.acmicpc.net
[ 문제풀이 ]
이 문제의 조건은 사이클이 없는 트리이기 때문에 주어지는 양방향 그래프를 단방향 트리로 먼저 바꾸어야 합니다. 그 후 dfs와 dp를 활용하여 문제를 풀어주면 됩니다.
먼저 각 노드별로 상태가 2가지(얼리어답터이거나 아니거나)씩 있습니다. 이를 활용하여 만약 현재 노드가 얼리어답터라면 다음 노드가 얼리어답터이든 아니든 큰 상관이 없습니다. 하지만 현재 노드가 얼리어답터가 아니라면 다음 노드는 무조건 얼리어답터이어야 합니다.
위의 조건을 이용하여 모든 노드들을 체크하면 최종 min(dfs(1,0), dfs(1,1))이 답이 됩니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include<iostream> #include<vector> #include<cstring> using namespace std; vector<int> list[1000001]; vector<int> tree[1000001]; int dp[1000001][2]; int visited[1000001]; int N; int ans = 987654321; int dfs(int node, int state) //상태에 따라 최솟값을 저장 { if (dp[node][state] != -1) return dp[node][state]; dp[node][state] = state; if (state == 0) { for (int i = 0; i < tree[node].size(); i++) { int next = tree[node][i]; dp[node][state] += dfs(next, 1); } } else { for (int i = 0; i < tree[node].size(); i++) { int next = tree[node][i]; dp[node][state] += min(dfs(next, 0), dfs(next, 1)); } } return dp[node][state]; } void makeTree(int node) //그래프를 트리로 재설정 { visited[node] = 1; for (int i = 0; i < list[node].size(); i++) { int next = list[node][i]; if (visited[next] != 1) { tree[node].push_back(next); makeTree(next); } } } int main() { cin >> N; for (int i = 0; i < N - 1; i++) { int u, v; scanf("%d %d", &u, &v); list[u].push_back(v); list[v].push_back(u); } makeTree(1); memset(dp, -1, sizeof(dp)); int ans = min(dfs(1, 0), dfs(1, 1)); cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 13334번 - 철로 (C++) (0) | 2022.06.29 |
|---|---|
| [ 백준 ] 14725번 - 개미굴 (C++) (0) | 2022.06.28 |
| [ 백준 ] 2162번 - 선분 그룹 (C++) (0) | 2022.06.26 |
| [ 백준 ] 2568번 - 전깃줄 - 2 (C++) (0) | 2022.06.25 |
| [ 백준 ] 14939번 - 불 끄기 (C++) (0) | 2022.06.24 |