[baekjoon] 1325 효율적인 해킹 (Javascript)

1325번: 효율적인 해킹 (acmicpc.net)

1325번: 효율적인 해킹

---

알고리즘 : dfs, 트리

 

이번 문제는 속도문제로 고생을 많이 했다.

고차함수를 사용하려고 forEach를 사용했는데 계속 시간초과가 발생했다.

n의 개수가 10000이라서 시간에 많이 부족한 문제였지만, 5초 제한으로 괜찮을 듯했다.

하지만, forEach는 시간초과, for loop는 정상 처리되는 것을 보니까 시간이 간당간당 한 것 같다.

 

일반 개발에서는 forEach를 사용하고 코딩테스트에서는 for loop를 많이 사용해야겠다.

 

let input = require("fs")
  .readFileSync("input.txt") //"/dev/stdin"
  .toString()
  .split("\n")
  .map((val) => val.trim());

let [n, m] = input
  .shift()
  .split(" ")
  .map((v) => +v);

input = input.map((v) => v.split(" ").map((val) => +val));

function solution() {
  let tree = {};
  input.forEach((v) => {
    let [from, to] = v;
    tree[to] ? tree[to].push(from) : (tree[to] = [from]);
  });

  let cnt = 0;
  let max = -1;
  let answer = [];
  const dfs = (node, vis) => {
    vis[node] = 1;
    cnt++;

    if (tree[node]) {
      for (let i = 0; i < tree[node].length; i++) {
        if (!vis[tree[node][i]]) {
          dfs(tree[node][i], vis);
        }
      }
    }
  };

  for (let i = 1; i <= n; i++) {
    let vis = new Array(n + 1).fill(0);
    cnt = 0;

    dfs(i, vis);

    if (cnt > max) {
      ans = [i];
      max = cnt;
    } else if (cnt === max) {
      ans.push(i);
    }
  }

  console.log(ans.sort((a, b) => a - b).join(" "));
}

solution();