백준 14627 < 회사 문화 1 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/14267

14267번: 회사 문화 1

 

📍알고리즘 분류

- 다이나믹 프로그래밍

- 그래프 이론

- 그래프 탐색

- 트리

- 깊이 우선 탐색

- 트리에서의 다이나믹 프로그래밍

 

📍문제 풀이

트리와 이차원 배열이 주어진다.

이차원 배열은 [정점 번호, 숫자] 형태의 원소를 갖고 있다.

이차원 배열을 순회하며, 정점 번호에 해당하는 정점의 모든 자식 노드에 숫자를 더해주면 된다.

 

- DFS를 사용하는 이유

사실 어차피 모든 그래프(트리)를 탐색해야 하기 때문에, BFS를 사용해도 무방할것 같다.

 

- DP를 사용해야 하는 이유

이차원 배열이 주어지면, 이차원 배열의 길이에 따라 1번씩 DFS가 발생해야 하는데, 이는 시간 복잡도를 매우 증가시킨다.

따라서 DFS를 1번만 사용하여 시간을 줄여야 한다.

 

그렇기 때문에, 이차원 배열을 이용하여 DFS로 각 정점을 탐색할 때마다, DP를 이용해 부모 노드의 누적값을 더해주면 된다.

 

📍코드 (JavaScript)

const [in1, in2, ...in3] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const [peopleNum, complimentNum] = in1.split(" ").map(Number);
const parentArr = in2.split(" ").map(Number);
const data = in3.map((el) => el.split(" ").map(Number));
const memo = Array(peopleNum).fill(0);

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  addEdge(v1, v2) {
    if (!this.adjacencyList[v1]) this.adjacencyList[v1] = [];
    this.adjacencyList[v1].push(v2);
  }

  dfs(start) {
    const stack = [start];
    while (stack.length) {
      const currentVertex = stack.pop();
      if (this.adjacencyList[currentVertex]) {
        this.adjacencyList[currentVertex].forEach((neighbor) => {
          stack.push(neighbor);
          // 모든 자식 노드에 부모 노드의 누적값을 더해줌
          memo[neighbor - 1] += memo[currentVertex - 1];
        });
      }
    }
  }
}

const g = new Graph();

// 정점, 간선 추가
for (let i = 1; i < peopleNum; i++) {
  g.addEdge(parentArr[i], i + 1);
}

// 각 직원이 받은 칭찬을 memo에 저장
for (let i = 0; i < complimentNum; i++) {
  const [person, weight] = data[i];
  memo[person - 1] += weight;
}
g.dfs(1);

console.log(memo.join(" "));

 

📍리뷰

- DFS + DP 콜라보 문제