C++로 모든 도시가 수도(0번 도시)에 도달하도록 도로 방향 재정렬하는 방법

0부터 n-1까지 번호가 매겨진 n개의 서로 다른 도시가 있고, 두 도시 사이를 이동할 수 있는 경로가 정확히 하나만 존재하는 n-1개의 도로가 있다고 가정해 보겠습니다. 즉, 전체 도로망은 트리(tree) 구조입니다.

교통부는 도로가 너무 좁기 때문에 모든 도로를 일방통행으로 만들기로 결정했습니다. 도로는 connections 배열로 표현되며, connections[i] = [a, b]는 도시 a에서 도시 b로 향하는 일방통행 도로를 의미합니다.

그런데 수도인 0번 도시에서 대규모 행사가 열려 많은 사람들이 이곳으로 이동하려고 합니다. 따라서 모든 도시에서 0번 도시에 도달할 수 있도록 일부 도로의 방향을 바꿔야 하며, 우리가 구해야 하는 것은 방향을 변경해야 하는 도로의 최소 개수입니다.

문제 예시

입력이 n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]라고 해보겠습니다.

이 경우 출력은 3입니다. 빨간색으로 표시된 간선들의 방향을 변경해야 모든 노드에서 수도로 이동할 수 있기 때문입니다.

접근 방법

핵심 아이디어는 BFS(너비 우선 탐색)를 활용하는 것입니다. 0번 도시에서 출발하여 인접한 도시들을 확장해 나가면서, 각 도시에 도달하기 위해 필요한 방향 변경 비용(dist)을 계산하고 그 합을 구합니다.

알고리즘 단계

크기 N = 5×10⁴ + 5의 두 개의 인접 리스트 graph1, graph2를 정의합니다.
각 간선 [a, b]에 대해:
- graph1[a]에 b를 추가합니다. (원래 방향: a → b)
- graph2[b]에 a를 추가합니다. (반대 방향: b → a)
크기 n의 dist 배열을 선언하고 큰 값(N + 10)으로 초기화합니다.
ret := 0, dist[0] := 0으로 설정합니다.
큐 q를 만들고 0을 삽입한 뒤, 방문 집합 visited에도 0을 추가합니다.
큐가 빌 때까지 다음을 반복합니다:
- 큐에서 노드를 꺼내고 ret += dist[node]를 수행합니다.
- graph2[node](node로 들어오는 간선)의 이웃은 방향 변경 없이 도달 가능하므로 dist[it] = 0으로 설정하고 큐에 삽입합니다.
- graph1[node](node에서 나가는 간선)의 이웃은 방향을 뒤집어야 도달 가능하므로 dist[it] = 1로 설정하고 큐에 삽입합니다.
모든 탐색이 끝나면 ret을 반환합니다.

C++ 구현 코드

다음 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
class Solution {
public:
    vector<int> graph1[N];
    vector<int> graph2[N];
    int minReorder(int n, vector<vector<int> >& e){
        map<int, int> in;
        for (auto& it : e) {
            graph1[it[0]].push_back(it[1]);
            graph2[it[1]].push_back(it[0]);
        }
        vector<int> dist(n, N + 10);
        int ret = 0;
        in[0] = 0;
        dist[0] = 0;
        queue<int> q;
        q.push(0);
        set<int> visited;
        visited.insert(0);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            ret += dist[node];
            for (auto& it : graph2[node]) {
                if (!visited.count(it) && dist[it] > 0) {
                    dist[it] = 0;
                    q.push(it);
                    visited.insert(it);
                }
            }
            for (auto& it : graph1[node]) {
                if (!visited.count(it) && dist[it] > 1) {
                    dist[it] = 1;
                    q.push(it);
                    visited.insert(it);
                }
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{0,1},{1,3},{2,3},{4,0},{4,5}};
    cout << (ob.minReorder(6,v));
}

입력

6,{{0,1},{1,3},{2,3},{4,0},{4,5}}

출력

복잡도 분석

이 알고리즘은 각 노드와 간선을 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 공간 복잡도 역시 인접 리스트와 큐, 방문 집합을 저장하기 위해 O(n)입니다. 트리 구조의 특성상 DFS를 사용해도 동일한 결과를 얻을 수 있습니다.