레야몬
[C++] 2533번 사회망 서비스(SNS) - 트리, DP 본문
#include <iostream>
#include <algorithm>
#include <vector>
#define FOR(i, k, N) for(int i=k; i<=N; i++)
#define MAX_N 1000001
#define INF 987654321
using namespace std;
int N; //친구 관계 트리의 정점 개수 N
vector<int> tr[MAX_N]; //트리
int vi[MAX_N]; //visited?
int dp[MAX_N][2]; //(색칠되지 않았는가? // 색칠되었는가?)
void input()
{
cin >> N;
FOR(i, 1, N-1) {
int u, v; cin >> u >> v;
tr[u].push_back(v); tr[v].push_back(u);
}
}
void DFS(int no)
{
vi[no]=1; //방문한 것 기록
FOR(i, 1, tr[no].size()) {
int next = tr[no][i-1];
if(!vi[next]) { //방문하지 않은 곳인 경우
DFS(next);
dp[no][0]+=dp[next][1]; //색칠 안되있으면 다음 노드가 색칠되어있어야 하고
dp[no][1]+=min(dp[next][0], dp[next][1]); //색칠되어있으면 상관 없음.
}
} dp[no][1]+=1; //자신이 색칠되어있으면 +1
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
input();
DFS(1);
cout << min(dp[1][0], dp[1][1]);
return 0;
}
사실 DP로 풀지 않고 0, 1, 0, 1로 풀어도 상관없었다는.... 그런 코드가 있었다는.... 그래서 아래에 적어놨다는...
굳이 DP로 풀지 않고 단순 DFS 탐색으로도 풀 수 있고 그러면 시간이 더 단축되어서 나온다.
<트리에서의 Dynamic Programming>
https://chanhuiseok.github.io/posts/algo-56/
알고리즘 - 트리 DP 문제 풀기(트리에서의 Dynamic Programming)
컴퓨터/IT/알고리즘 정리 블로그
chanhuiseok.github.io
<참고한 코드(풀어야 볼 수 있습니다.)>
https://www.acmicpc.net/source/7093213
로그인
www.acmicpc.net
※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.
'알고리즘 > 백준' 카테고리의 다른 글
[C++] 1007번 벡터 매칭 - 수학, 브루트포스 (0) | 2022.10.07 |
---|---|
[C++] 1761번 정점들의 거리 - 트리, 최소 공통 조상, 희소 배열 (0) | 2022.10.06 |
[C++] 2618번 경찰차 - DP (0) | 2022.10.05 |
[C++] 2357번 최솟값과 최댓값 - 자료 구조, 세그먼트 트리 (0) | 2022.10.05 |
[C++] 2150번 Strongly Connected Component - 그래프 이론, 강한 연결 요소 (0) | 2022.10.05 |
Comments