[백준] 14967 영우는 사기꾼? - javascript

📌 문제

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

📌 풀이

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

let [n, m, k] = input[0].split(" ").map(Number);
let indegrees = new Array(n + 1).fill(0);
let graph = new Array(n + 1);
for (let i = 0; i < graph.length; i++) {
  graph[i] = [];
}
let building_num = new Array(n + 1).fill(0);
for (let i = 0; i < m; i++) {
  let [from, to] = input[i + 1].split(" ").map(Number);
  graph[from].push(to);
  indegrees[to]++;
}

let flag = true;
for (let i = 0; i < k; i++) {
  let [a, b] = input[i + m + 1].split(" ").map(Number);
  if (a === 1) {
    // 건설
    if (indegrees[b] !== 0) {
      flag = false;
      break;
    } else {
      if (building_num[b] === 0) {
        for (let j = 0; j < graph[b].length; j++) {
          indegrees[graph[b][j]]--;
        }
      }
      building_num[b]++;
    }
  } else {
    // 파괴
    if (building_num[b] === 0) {
      flag = false;
      break;
    }
    if (building_num[b] === 1) {
      for (let j = 0; j < graph[b].length; j++) {
        indegrees[graph[b][j]]++;
      }
    }
    building_num[b]--;
  }
}
if (flag) {
  console.log("King-God-Emperor");
} else {
  console.log("Lier!");
}

✔ 알고리즘 : 위상정렬

✔ 간선 정보를 입력받으면서 graph를 구현하고 indegrees 배열을 통해 어떠한 건물이 건설하기 위해 필요한 이전 건물의 수를 저장한다.

✔ 정보를 탐색

• a가 1 인 경우 (건물 건설)
  • indegrees[b]가 0이 아닌 경우
    b건물을 건설하기 위해서는 indegrees[b]가 0이여야 한다. 0이 아닌 경우 치트키를 쓴 경우이므로 flag를 false로 바꿔주고 break
  • indegrees[b]가 0인 경우
    • 현재 b건물이 하나도 없는 경우
      b로부터 뻗어나가는 graph를 탐색하며 indegrees를 1씩 감소시킨 후 b건물의 수를 1증가
    • 현재 b건물이 존재하는 경우
      b건물의 수를 1증가
• a가 2 인 경우 (건물 파괴)
  • building_num[b]가 0인 경우
    건물이 없는데 파괴하는 경우는 치트키를 쓴 경우이므로 flag를 false로 바꿔주고 break
  • building_num[b]가 1인 경우
    b로부터 뻗어나가는 graph를 탐색하며 indegrees를 1씩 증가시킨 후 b건물의 수를 1감소
  • building_num[b]가 2 이상인 경우
    b건물의 수를 1 감소

✔ flag가 true인 경우 치트키를 쓰지 않은 경우이다.

✔ 난이도 : 백준 기준 골드 4