코딩테스트/백준
[백준 | Java] 2533번 사회망 서비스(SNS)
박 성 하
2024. 2. 9. 19:18
728x90
문제
https://www.acmicpc.net/problem/2533
2533번: 사회망 서비스(SNS)
첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에
www.acmicpc.net
티어
분류
dfs
dp
코드
public class Main {
static int n;
static ArrayList<Integer>[] graph;
static boolean[] visited;
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
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++) {
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
graph[v1].add(v2);
graph[v2].add(v1);
}
dp = new int[n + 1][2];
visited = new boolean[n + 1];
dfs(1);
System.out.println(Math.min(dp[1][0], dp[1][1]));
}
private static void dfs(int idx) {
visited[idx] = true;
dp[idx][0] = 1;
dp[idx][1] = 0;
for (Integer vertex : graph[idx]) {
if (!visited[vertex]) {
dfs(vertex);
dp[idx][0] += Math.min(dp[vertex][0], dp[vertex][1]);
dp[idx][1] += dp[vertex][0];
}
}
}
}
코드 설명
문제에서 가장 조심해야할 부분은 루트노드가 1이 아닐 수도 있다는 것이다.
이 부분 때문에 문제는 트리라고 했지만 그래프로 푸는 것이 더 쉽다.
따라서 그래프를 선언하고 간선과 연결된 모든 정점 (부모, 자식)을 모두 동일 선상에 연결한다.
public static void main(String[] args) throws IOException {
//...
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
graph[v1].add(v2);
graph[v2].add(v1);
}
//...
}
아이디어는 다음과 같다.
1️⃣ 부모가 얼리어답터가 아닐 경우, 자식은 무조건 얼리어답터여야 한다.
2️⃣ 부모가 얼리어답터일 경우, 자식은 얼리어답터일 수도 있고 얼리어답터가 아닐 수도 있다.
dp가 들고 있는 값은 현재 노드까지 얼리어답터인 노드의 개수를 저장해야하고, 부모의 dp값을 계산하기 위해서는 자식의 dp값이 필수적이기 때문에 리프노드부터 값을 구해나가야 한다.
dp[idx][0] -> idx번 노드가 얼리어답터
dp[idx][1] -> idx번 노드가 얼리어답터가 아님
private static void dfs(int idx) {
//...
for (Integer vertex : graph[idx]) {
//...
dfs(vertex);
//idx번 노드가 얼리어답터이므로 자식(vertex)는 얼리어답터일 수도 있고, 아닐 수도 있음
dp[idx][0] += Math.min(dp[vertex][0], dp[vertex][1]);
//idx번 노드가 얼리어답터이므로 자식은 얼리어답터
dp[idx][1] += dp[vertex][0];
}
}
728x90