[C++] 백준 2533번 사회망 서비스(SNS)

[C++] 백준 2533번 사회망 서비스(SNS)

최소한의 얼리어댑터를 통해서 모든 사람에게 전파할 수 있는지 찾는 문제입니다.

DP와 DFS방식을 사용하여 문제를 해결하였습니다.

case1 : 현재 탐색중인 노드가 얼리어댑터인 경우

=> 이웃한 노드는 얼리어댑터일수도 아닐수도 있습니다.

case2 : 현재 탐색중인 노드가 얼리어댑터가 아닌 경우

=> 이웃한 노드는 얼리어댑터이어야 합니다.

check[1000001][2]

1000001 => 100만명의 사람에 대한

2 => 0 : 얼리어댑터가 아님, 1 : 얼리어댑터가 맞음

이를 식으로 바꾸면 다음과 같습니다.

check[now][0] += check[next][1]; //case1 check[now][1] += min(check[next][0], check[next][1]); //case2

#include #include #include using namespace std; bool visit[1000001]; int check[1000001][2]; vector > v; void dfs(int now) { int next; visit[now] = true; check[now][1] = 1; for(int i=0; i> n; v.resize(n + 1); for(int i=1; i> a >> b; v[a].push_back(b); v[b].push_back(a); } dfs(1); cout << min(check[1][0], check[1][1]) << endl;; return 0; }

728x90

from http://j3sung.tistory.com/787 by ccl(A) rewrite - 2021-08-25 22:00:41