[백준2533_자바스크립트(javascript)] - 사회망 서비스(SNS)

🔴 문제

사회망 서비스(SNS)

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n], ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

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

for (const [u, v] of inputs) {
  graph[u].push(v);
  graph[v].push(u);
}

const dfs = (node) => {
  visited[node] = true;

  for (const child of graph[node]) {
    if (!visited[child]) {
      dfs(child);

      dp[node][0] += dp[child][1];
      dp[node][1] += Math.min(dp[child][0], dp[child][1]);
    }
  }
};

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

🟢 풀이

⏰ 소요한 시간 : -

트리 DP 유형이다. 사실 트리 DP는 처음 풀어봐서 지피티의 도움을 받았다.
dp 배열은 아래와 같이 정의한다.

dp[n][0|1] : n번사람이 얼리어답터가 아니거나(0), 얼리어답터일 경우(1) 필요한 최소 얼리어답터의 수

먼저 친구 관계를 입력으로 받아준다. 친구 관계 트리구조는 무방향 그래프기 때문에 기본적으로 양방향 그래프로 입력받아준다.
그 후, 트리구조의 끝부터 탐색하기위해 dfs를 수행해준다. dfs는 후위 순회 방식으로 동작하고, 자식 노드의 값을 먼저 계산한 뒤 부모 노드의 값을 업데이트 하기 때문에 dp배열을 올바르게 업데이트 할 수 있다.

아무튼 말단자식노드에 도달하면 dp 배열을 업데이트 시켜주는데 현재 노드가 얼리어답터가 아니라면 나와 연결된 부모노드가 반드시 얼리어답터여야 하므로 아래와 같이 식을 세울 수 있다.

dp[node][0] += dp[child][1];

만약 현재 노드가 얼리어답터라면 부모 노드가 얼리어답터이든 아니든 상관없다. 둘 중 더 작은 값을 찾아 dp배열을 업데이트하면 된다.

dp[node][1] += Math.min(dp[child][0], dp[child][1]);

🔵 Ref