[백준] #2533 사회망 서비스(SNS) 문제 풀이 | G3 | Node.js

문제 링크 : https://www.acmicpc.net/problem/2533

문제 정보

문제 해결

문제 개요 

백준 2533번 사회망 서비스(SNS) 문제는 트리 형태의 SNS 네트워크에서 모든 사람이 최소한 한 명의 얼리 어답터(Early Adopter)와 연결되도록 하는 최소 얼리 어답터 수를 구하는 문제입니다.

• 노드(사용자)들은 트리 형태로 연결되어 있습니다.
• 각 사용자는 얼리 어답터(새로운 기술을 먼저 사용하는 사람) 또는 일반 사용자일 수 있습니다.
• 최소한의 얼리 어답터를 선정하여 모든 일반 사용자가 최소 한 명의 얼리 어답터와 연결되도록 해야 합니다.

해결 방법

이 문제는 트리 DP(Tree DP) 기법을 활용하여 해결하였습니다.

• 각 노드(사용자)가 얼리 어답터인 경우와 아닌 경우를 나눠서 탐색합니다.
• DFS(깊이 우선 탐색)를 이용하여 서브트리의 정보를 DP 배열에 저장하면서 최소 얼리 어답터 수를 계산합니다.

DFS + DP 탐색 로직

function dfs(cur) {
  visited[cur] = true;
  dp[cur][1] = 1;

  for (let next of node[cur]) {
    if (visited[next]) continue;
    dfs(next);
    dp[cur][0] += dp[next][1];
    dp[cur][1] += Math.min(dp[next][0], dp[next][1]);
  }
}

1. cur 노드를 방문 처리하고, cur이 얼리 어답터인 경우(dp[cur][1])를 1로 설정합니다.
2. cur의 자식 노드(next) 를 DFS 탐색합니다.
3. 얼리 어답터가 아닌 경우(dp[cur][0]):
   • 자식 노드는 무조건 얼리 어답터여야 함 👉 dp[cur][0] += dp[next][1]
4. 얼리 어답터인 경우(dp[cur][1]):
   • 자식 노드는 얼리 어답터일 수도, 아닐 수도 있음 👉 dp[cur][1] += min(dp[next][0], dp[next][1])

 

최종 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const n = Number(input[0]);

const node = Array.from({ length: n + 1 }, () => []);
const visited = Array(n + 1).fill(false);
const dp = Array.from({ length: n + 1 }, () => [0, 0]);

for (let i = 1; i < n; i++) {
  const [a, b] = input[i].split(" ").map(Number);
  node[a].push(b);
  node[b].push(a);
}

dfs(1);

console.log(Math.min(dp[1][0], dp[1][1]));

function dfs(cur) {
  visited[cur] = true;
  dp[cur][1] = 1;

  for (let next of node[cur]) {
    if (visited[next]) continue;
    dfs(next);
    dp[cur][0] += dp[next][1];
    dp[cur][1] += Math.min(dp[next][0], dp[next][1]);
  }
}