728x90
반응형
2533 - 사회망 서비스(SNS)
https://www.acmicpc.net/problem/2533


문제
사회망에서 사람들의 친구 관계 그래프로 표현 (사이클 X)
(사람 -> 정점 / 두 사람이 서로 친구 관계 -> 정점을 잇는 에지)
-> 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정 이해
얼리 어답터(early adaptor): 어떤 새로운 아이디어를 먼저 받아들인 사람
/ 얼리 어답터가 아닌 사람은 자신의 모든 친구들이 얼리 어답터일 때만 이 아이디어 받아들임
=> 친구 관계 트리가 주어졌을 때 모든 개인이 새로운 아이디어를 수용하기 위해 필요한 최소 얼리 어답터 수?
입력
첫째 줄: 친구 관계 트리의 정점 개수 N (2 <= N <= 1,000,000, 각 정점 1 ~ N까지 일련번호로 표현)
두 번째 줄 N - 1개의 줄: 각 줄마다 친구 관계 트리의 에지(u, v) 나타내는 두 정수
출력: 아이디어 전파하는데 필요한 얼리 어답터의 최소 수
풀이
DFS + DP
- `dp[v][0]`: v가 얼리어답터 X -> 필요한 최소 얼리어답터 수
- 자식 노드 반드시 얼리어답터야 함
-> `dp[v][0] += dp[child][1]`
- 자식 노드 반드시 얼리어답터야 함
- `dp[v][1]`: v가 얼리어답터 O -> 필요한 최소 얼리어답터 수
- 자식 얼리어답터이든 아니든 상관 X
-> `dp[v][1] += min(dp[child][0], dp[child][1])`
- 자식 얼리어답터이든 아니든 상관 X
-> 부모-자식 간의 의존 관계
/ 자식의 dp 먼저 계산해야 부모 dp 채울 수 있음 -> 후위 순회(DFS)
=> 트리 DP 패턴 = DFS 기반 하향식 DP
static void dfs(int v) {
visited[v] = true;
dp[v][0] = 0;
dp[v][1] = 1;
for (int next : graph[v]) {
if (!visited[next]) {
dfs(next);
dp[v][0] += dp[next][1];
dp[v][1] += Math.min(dp[next][0], dp[next][1]);
}
}
}
코드
import java.io.*;
import java.util.*;
// 사회망 서비스(SNS)
public class boj_2533 {
static int N;
static List<Integer>[] graph;
static int[][] dp;
static boolean[] visited;
static void dfs(int v) {
visited[v] = true;
dp[v][0] = 0;
dp[v][1] = 1;
for (int next : graph[v]) {
if (!visited[next]) {
dfs(next);
dp[v][0] += dp[next][1];
dp[v][1] += Math.min(dp[next][0], dp[next][1]);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
graph = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < N - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
graph[u].add(v);
graph[v].add(u);
}
dp = new int[N + 1][2];
visited = new boolean[N + 1];
dfs(1);
System.out.println(Math.min(dp[1][0], dp[1][1]));
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/MST] 백준 1647 - 도시 분할 계획 (Java) (0) | 2025.11.11 |
|---|---|
| [BOJ] 백준 2252 - 줄 세우기 (Java) (0) | 2025.11.11 |
| [BOJ/BFS] 백준 16954 - 움직이는 미로 탈출 (Java) (0) | 2025.11.10 |
| [BOJ/Union-Find] 백준 4195 - 친구 네트워크 (Java) (0) | 2025.11.10 |
| [BOJ/Union-Find] 백준 1717 - 집합의 표현 (Java) (0) | 2025.11.09 |