문제 개요

문제: 키 순서

분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 최단 경로, 플로이드-워셜

난이도: 골드4

문제 풀이

자신의 키가 몇 번째인지 알기 위해서는 자신보다 키가 더 작은 학생의 수와 더 큰 학생의 수를 정확히 알아야 한다.
이를 위해 모든 학생에 대해 해당 학생을 시작점으로 하는 DFS를 수행한다.

• 방문하는 노드의 개수(=DFS 함수가 재귀적으로 호출된 횟수)가 해당 학생보다 키가 큰 학생의 수가 된다.
• 해당 학생은 방문하는 모든 노드들보다 키가 작다.
  따라서 방문하는 노드(학생)들은 자신보다 키가 작은 학생의 수를 1명 카운트한다.

DFS 수행이 모두 끝난 후 아래의 경우에 해당하는 학생만 정답으로 카운트한다.

• 자신보다 키가 더 작은 학생의 수 + 키가 더 큰 학생의 수 = 전체 학생 수-1

자신을 제외한 나머지 학생이 자기보다 큰지 작은지를 빠짐없이 다 알고 있다면 자신의 키 순서를 정확히 아는 것이다.

아래 그림은 예제 입력 1에서 1번 학생을 시작으로 DFS를 진행하는 과정이다.

smallerCnt = 자신보다 키가 작은 학생의 수를 저장하는 배열,
biggerCnt = 자신보다 키가 큰 학생의 수를 저장하는 배열

1번 노드에서 방문할 수 있는 노드는 5번 노드이다.

• 5번 학생보다 1번 학생의 키가 작다. 따라서 smallerCnt[5]에 1만큼 더한다.
• 1번 학생보다 5번 학생의 키가 크다. 따라서 biggerCnt[1]에 1만큼 더한다.

5번 노드에서 방문할 수 있는 노드는 4번 노드이다.

• 4번 학생보다 1번 학생의 키가 작다. 따라서 smallerCnt[4]에 1만큼 더한다.
• 1번 학생보다 4번 학생의 키가 크다. 따라서 biggerCnt[1]에 1만큼 더한다.

마찬가지로 4번 노드에서 방문할 수 있는 노드는 2번, 6번 노드이다.

• 2, 6번 학생보다 1번 학생의 키가 작다. 따라서 smallerCnt[2]와 smallerCnt[6]에 1만큼 더한다.
• 1번 학생보다 2, 6번 학생의 키가 크다. 따라서 biggerCnt[1]에 각각 1만큼 더한다.

모든 학생에 대해 DFS를 끝내고 나면 smallerCnt와 biggerCnt 배열은 다음과 같이 채워진다.

	1	2	3	4	5	6
smallerCnt	0	4	0	3	1	4
biggerCnt	4	0	3	2	3	0

n번 학생에 대해 smallerCnt[n]과 biggerCnt[n]의 합이 전체 학생 수-1과 같은 학생은 4번 학생 1명 뿐이므로 정답은 1이 된다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M] = input.shift().split(" ").map(Number);
const height = input.map((v) => v.split(" ").map(Number));

const solution = (N, M, height) => {
  const graph = Array.from(Array(N + 1), () => []);
  const smallerCnt = new Array(N + 1).fill(0);
  const biggerCnt = new Array(N + 1).fill(0);
  let depth, visited;
  let answer = 0;

  const makeGraph = (height) => {
    height.forEach(([A, B]) => {
      graph[A].push(B);
    });
  };

  const dfs = (curr) => {
    depth++;

    for (let i = 0; i < graph[curr].length; i++) {
      const next = graph[curr][i];
      if (visited[next]) continue;
      visited[next] = true;
      smallerCnt[next]++;
      dfs(next);
    }
  };

  makeGraph(height);

  for (let i = 1; i <= N; i++) {
    visited = new Array(N + 1).fill(false);
    depth = 0;
    visited[i] = true;
    dfs(i);
    biggerCnt[i] = depth - 1;
  }

  for (let i = 1; i <= N; i++) {
    if (smallerCnt[i] + biggerCnt[i] === N - 1) answer++;
  }

  console.log(answer);
};

solution(N, M, height);