[LeetCode] 1466. Reorder Routes to Make All Paths Lead to the City Zero, Medium

1. 문제

• 도시의 수 n이 주어지고, 도시 간의 연결 도로 정보 2차원 배열이 주어질 때 모든 도시에서 0번 도시로 갈 수 있도록 변경해야하는 도로의 수를 반환하라.

2. 해결

function minReorder(n: number, connections: number[][]): number {
    const visited = new Array(n).fill(false);
    const map = new Map<number, number[][]>();

    let count = 0;

    for (const [from, to] of connections) {
        map.set(from, (map.get(from) || []).concat([[to, 1]])); 
        map.set(to, (map.get(to) || []).concat([[from, 0]]));  
    }

    function DFS(node: number) {
        visited[node] = true;

        for(const [nextNode, isOriginal] of map.get(node) || []) {
            if(!visited[nextNode]) {
                if(isOriginal === 1) count++;
                DFS(nextNode);
            }
        }
    }

    DFS(0)

    return count;  
};

• 일단 못풀었는데, 방문 배열과 map을 통해 노드 연결 정보를 구성하는 데 까지는 접근했다.
• 이 때 방향 정보를 어떻게 알 수 있을까 고민하다가 다른 풀이를 참고했다.
• 방향 정보를 1과 0으로 두고, 노드와 함께 묶어 map에 2차원 배열 형태로 저장한다.
• 이 때, 1은 해당 노드에서 나가는 방향의 정보고 0은 해당 노드로 들어오는 방향의 정보다.
• 이 상태에서 0번 노드부터 탐색을 시작하면 우리가 고려해야 할 것은 나가는 방향의 정보만을 고려하면 된다.