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

김준수·2024년 4월 2일
0

LeetCode 75

목록 보기
45/63
post-custom-banner

Description

There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

It's guaranteed that each city can reach city 0 after reorder.


1466. 모든 경로가 도시 0으로 이어지도록 경로 재정렬하기

0번에서 n - 1번까지 번호가 매겨진 n개의 도시와 서로 다른 두 도시 간에 이동할 수 있는 한 가지 방법만 있는 n - 1개의 도로가 있습니다(이 네트워크는 트리 형태를 이룹니다). 작년에 교통부는 도로가 너무 좁기 때문에 도로를 한 방향으로 정하기로 결정했습니다.

도로는 connections에 의해 표현되며 connections[i] = [ai, bi]는 도시 ai에서 도시 bi로의 도로를 나타냅니다.

올해는 수도(도시 0)에서 큰 행사가 열릴 예정이며, 많은 사람들이 이 도시로 여행하고자 합니다.

당신의 임무는 몇몇 도로의 방향을 재설정하여 각 도시가 도시 0을 방문할 수 있도록 하는 것입니다. 변경해야 할 최소한의 도로 수를 반환하세요.

각 도시가 재정렬 후에 도시 0에 도달할 수 있다는 것이 보장됩니다.

예제 1:

  • 입력: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
  • 출력: 3
  • 설명: 각 노드가 노드 0(수도)에 도달할 수 있도록 빨간색으로 표시된 도로의 방향을 변경합니다.

예제 2:

  • 입력: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
  • 출력: 2
  • 설명: 각 노드가 노드 0(수도)에 도달할 수 있도록 빨간색으로 표시된 도로의 방향을 변경합니다.

예제 3:

  • 입력: n = 3, connections = [[1,0],[2,0]]
  • 출력: 0

제약 조건:

  • 2 <= n <= 5 * 10^4
  • connections.length == n - 1
  • connections[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi

Solution


public class Solution {
    public int minReorder(int n, int[][] connections) {
        // 각 노드에서 출발하는 간선 리스트를 저장할 그래프 초기화
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 각 연결을 그래프에 추가
        for (int[] connection : connections) {
            int from = connection[0];
            int to = connection[1];
            graph.get(from).add(new int[] { to, 1 }); // 방향성 있는 간선
            graph.get(to).add(new int[] { from, 0 }); // 방향성 없는 간선
        }

        boolean[] visited = new boolean[n];
        return dfs(0, graph, visited);
    }

    private int dfs(int node, List<List<int[]>> graph, boolean[] visited) {
        visited[node] = true;
        int count = 0;

        for (int[] edge : graph.get(node)) {
            if (!visited[edge[0]]) {
                count += edge[1]; // 방향성 있는 간선일 경우 카운트 증가
                count += dfs(edge[0], graph, visited);
            }
        }

        return count;
    }
}

post-custom-banner

0개의 댓글