[프로그래머스] 빠른 이동 (JavaScript)

문제 설명[링크]

현대모비스의 주행시험장 트랙을 주행해 볼 수 있는 가상 시뮬레이션 프로그램이 있습니다. 시뮬레이션의 트랙에는 1 ~ n의 서로 다른 번호가 붙은 지점이 n개 있으며, 각 지점마다 고유한 스탬프가 있습니다. 각 지점을 방문할 때 해당 지점의 스탬프를 얻을 수 있습니다. 당신은 1번 지점에서 시작하여 각 지점을 최소 한 번씩 방문해 n가지 스탬프를 모두 모으려 합니다.

지점들은 m개의 단방향 도로로 연결되어 있습니다. 당신은 지점 사이를 이동하기 위해 단방향 도로를 이용할 수 있습니다.

다음은 n = 6인 예시입니다.

• 각 원은 지점을 나타내며, 원 안에 적힌 수는 지점의 번호를 나타냅니다.
• 화살표는 두 지점을 연결하고 있는 단방향 도로를 나타냅니다.

위 예시에서 1번 지점에서 출발해 1 - 2 - 6과 같은 경로로 움직이면 1, 2, 6번 지점의 스탬프 3가지를 모을 수 있습니다. 하지만 6번 지점에 도착하면 더 이상 이용할 수 있는 도로가 없습니다.

시뮬레이션에는 단방향 도로를 이용하는 것 외의 이동 방법으로 빠른 이동 기능이 있습니다. 빠른 이동이란 당신이 스탬프를 얻은 지점 중 원하는 곳으로 순간 이동할 수 있는 기능입니다. 예를 들어 위 예시에서 1 - 2 - 6 - 2(빠른 이동) - 4 - 3 - 5와 같은 경로로 움직이면 모든 지점을 한 번씩 방문해 n가지 스탬프를 모두 모을 수 있습니다.

당신은 n가지 스탬프를 모두 모으기 위해 필요한 빠른 이동의 최소 사용 횟수를 알고 싶습니다.

지점의 수를 나타내는 정수 n과 지점을 연결하는 단방향 도로들의 정보를 담고 있는 2차원 정수 배열 roads가 매개변수로 주어집니다. 이때, 1번 지점에서 출발해 n가지 스탬프를 모두 모으기 위해 필요한 빠른 이동의 최소 사용 횟수를 return 하도록 solution 함수를 완성해 주세요.

풀이

/* eslint-disable no-continue */
/* eslint-disable no-param-reassign */
class UnionFind {
  constructor(size) {
    this.parent = new Array(size);
    this.rank = new Array(size);

    for (let i = 0; i < size; i += 1) {
      this.parent[i] = i;
      this.rank[i] = 0;
    }

    this.rank[1] = Infinity;
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX !== rootY) {
      if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else {
        this.parent[rootY] = rootX;
        this.rank[rootX] += 1;
      }
    }
  }

  getUniques() {
    return this.parent.filter((el, index) => (index !== 0 && el === index));
  }
}

function solution(n, roads) {
  const uf = new UnionFind(n + 1);
  const towardGroups = new Array(n + 1).fill().map((_) => []);

  for (const [from, to] of roads) {
    towardGroups[from].push(to);
  }

  const visited = new Array(n + 1).fill(0);
  const stackIndex = new Array(n + 1).fill(null);
  stackIndex[1] = 0;
  visited[1] = 1;

  const dfs = (curIndex, stack) => {
    const towardGroup = towardGroups[curIndex];

    for (const towardIndex of towardGroup) {
      const prefixedTowardIndex = uf.find(towardIndex);
      if (!visited[prefixedTowardIndex]) {
        visited[prefixedTowardIndex] = 1;
        stack.push(prefixedTowardIndex);
        stackIndex[prefixedTowardIndex] = stack.length - 1;
        dfs(prefixedTowardIndex, stack);
        stack.pop();
        stackIndex[prefixedTowardIndex] = null;
      } else {
        const index = stackIndex[prefixedTowardIndex];

        if (index !== null) {
          const value = stack[index];
          const rootValue = uf.find(value);
          uf.rank[rootValue] = Infinity;

          for (let i = index + 1; i < stack.length; i += 1) {
            uf.union(value, stack[i]);
          }
        }
      }
    }
  };

  dfs(1, [1]);

  const prefixTowardGroups = new Array(n + 1).fill().map((_) => []);

  for (const [from, to] of roads) {
    const prefixedFrom = uf.find(from);
    const prefixedTo = uf.find(to);

    if (prefixedFrom !== prefixedTo) {
      prefixTowardGroups[prefixedFrom].push(prefixedTo);
    }
  }

  const towardDirectly = new Array(n + 1);

  const visited2 = new Array(n + 1).fill(0);
  const dfs2 = (x) => {
    let directTowardGroup = new Set();
    visited2[x] = 1;
    const towardGroup = prefixTowardGroups[x];

    for (const toward of towardGroup) {
      directTowardGroup.add(toward);
      if (!visited2[toward]) {
        directTowardGroup = new Set([...directTowardGroup, ...dfs2(toward)]);
      } else {
        directTowardGroup = new Set([...directTowardGroup, ...towardDirectly[toward]]);
      }
    }

    towardDirectly[x] = directTowardGroup;
    return directTowardGroup;
  };

  dfs2(1);

  const uniques = uf.getUniques();
  const fromDirectly = new Array(n + 1).fill().map(() => new Set());

  for (const unique of uniques) {
    for (const el of towardDirectly[unique]) {
      fromDirectly[el].add(unique);
    }
  }

  const assigns = new Array(n + 1).fill(0);

  const bMatching = (x, memo) => {
    const fromGroup = fromDirectly[x];

    for (const from of fromGroup) {
      if (memo[from]) continue;

      memo[from] = 1;

      if (!assigns[from] || bMatching(assigns[from], memo)) {
        assigns[from] = x;

        return true;
      }
    }

    return false;
  };

  let result = 0;

  for (const unique of uniques) {
    if (bMatching(unique, new Array(n + 1).fill(0))) {
      result += 1;
    }
  }
  return uniques.length - result - 1;
}

결과