[BOJ] 14676 영우는 사기꾼? | 위상정렬

Problem | 영우는 사기꾼?

✨ 접근 방식

indegree 라는 n+1 배열을 만든다.
자신에게 들어오는 갯수를 체크한다. ( 노드 2의 경우 1에서 들어오는 경우 1이고, 노드 4인 경우 2, 3 에서 들어오는 경우 2이다.)

• 건설 가능한 경우
  indegree가 0인 경우다.
  ( 아직 건설되지 않은 경우 : 건설시켜주고, 건설된 건물이 가지고 있는 간선들의 indegree를 하나씩 뺴준다. => 1이 건설된다면 indegree[2] , indegree[3]의 값이 하나씩 빠지는 셈이다. )
  ( 건설 된 경우 : 추가적으로 건설시켜주면 된다. )

• 파괴 가능한 경우
  이미 built된 경우다.
  (건설된 수가 1보다 크다면, 건설 된 수만 줄여준다. => 같은 건물 여러 개 건설 가능)
  (건설된 수가 1이라면 파괴한 애들의 간선들의 indegree를 하나씩 더해준다.
  => 만약, 2가 파괴되었는데 4를 설치할 수 없기 때문이다. )

- ✔️ 전체코드

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

let [n, m, k] = inputs[0].split(" ").map(Number);

let graph = Array.from(Array(n + 1), () => new Array());
let indegree = new Array(n + 1).fill(0);

// built 변수 : 건물을 세웠는지 안세웠는지 체크한다.
let built = new Array(n + 1).fill(0);

for (let i = 0; i < m; i++) {
  let [nx, ny] = inputs[1 + i].split(" ").map(Number);
  graph[nx].push(ny);
  indegree[ny]++;
}

function solution() {
  for (let i = 0; i < k; i++) {
    let [nx, ny] = inputs[1 + m + i].split(" ").map(Number);

    if (nx === 1) {
      // 건설하는 경우
      if (indegree[ny] === 0) {
        // 건설가능 경우
        if (built[ny] === 0) {
          // 아직 건설 안된 경우
          for (let next of graph[ny]) indegree[next]--;
        }
        built[ny]++;
      } else {
        return "Lier!";
      }
    } else {
      if (built[ny] !== 0) {
        // 이미 건설된 경우
        built[ny]--;
        if (built[ny] === 0) {
          for (let next of graph[ny]) indegree[next]++;
        }
      } else {
        return "Lier!";
      }
    }
  }
  return "King-God-Emperor";
}

console.log(solution());