1466. Reorder Routes to Make All Paths Lead to the City Zero

Leetcode 1466번 풀이

문제

Reorder Routes to Make All Paths Lead to the City Zero

풀이

아이디어

n-1개의 단방향 간선으로 이루어진 트리에서, 모든 노드가 0번 노드에 도달할 수 있도록 최소한의 간선 방향을 바꾸는 문제다.

모든 노드가 0번 노드에 도달할 수 있다는 것은 반대로 0번 노드가 모든 노드에 도달할 수 있다는 뜻이기도 하다. 자연스럽게 0번 노드를 루트로 하고 다른 노드들이 자식 노드가 되는 트리 모양을 떠올릴 수 있다.

단방향 간선이 주어지지만 우리는 양방향으로 탐색하면서 방향을 직접 바꿔줘야 하기 때문에 주어진 간선을 방향과 함께 단방향으로 저장해줬다. 그리고 0번 노드부터 BFS로 탐색하면서, 탐색하는 방향이 원래 간선의 방향과 일치한다면 그 간선은 방향을 바꿔줘야 하는 간선이므로 세어줬다.

코드

function minReorder(n: number, connections: number[][]): number {
  // 0에서부터 다른 도시로 모두 이동할 수 있게 하기
  // 길에는 방향이 있다.
  // 루트인 0으로부터 다른 도시로 (leaf) 이동할 수 있게 해주면 됨
  // ---

  // 길 정보 저장하기
  const roads = new Map(); // key : 시작점, value : [끝점, 방향 ('original' | 'reverse')]
  for (const connection of connections) {
    const [from, to] = connection;
    // 한줄로 표현하고 싶어서 억지로 작성했는데, 이렇게 하면 매번 배열을 생성해서 비효율적이다.
    roads.set(from, [...(roads.get(from) ?? []), [to, 'original']]);
    roads.set(to, [...(roads.get(to) ?? []), [from, 'reverse']]);
  }

  // 0부터 시작해서 탐색하기... bfs로.
  let answer = 0;
  const visited = new Set([0]);
  const queue = [0]; // 현재 노드
  let front = 0;

  while (front < queue.length) {
    const curr = queue[front++];
    const currRoads = roads.get(curr);
    for (const road of currRoads) {
      const [to, dir] = road;
      if (visited.has(to)) continue;
      visited.add(to);
      if (dir === 'original') answer++; // 잊지 말기! 우리는 지금 0에서 멀어지는 방향으로 탐색 중!
      queue.push(to);
    }
  }

  return answer;
}

시간 / 공간 복잡도

• 시간 복잡도: O(N) — 노드 수 N에 대해 각 노드와 간선을 한 번씩 방문
• 공간 복잡도: O(N) — 인접 리스트, 방문 집합, 큐 모두 O(N)