Reorder Routes to Make All Paths Lead to the City Zero(leetcode, 1466)

문제 설명

방향 그래프가 주어졌을 떼 모든 노드가 0으로 가기 위해서 얼마나 적은 도로의 방향을 바꾸어야 하는지 구하는 문제다.

문제 풀이

첫 번째 접근

hint

그래프를 무방향으로 생각하세요. 루트에서부터 dfs를 시작하는데, 만일 당신이 정방향(앞으로 가는 거, foward)으로 edge를 이동한다면 당신은 edge를 바꾸어야 합니다.

여기서 중요한 건 너무 방향에 집중해서 안 된다는 것이다. 일단 양방향 그래프를 만든다고 생각해야 한다. 원래 주어진 방향은 본래 그래프처럼 그리지만, 역방향 그래프는 음수를 붙여서 역방향임을 표현한다.

이렇게 되면 양수 노드는 해당 부모 노드에서 나가는 자식 노드가 될 것이고 음수 노드는 해당 부모 노드로 들어가는 자식 노드가 될 것이다. 여기까지 하면 거의 다 푼 것이나 마찬가지다.

이제 0부터 그래프를 탐색한다. 만일 해당 노드를 방문하지 않았다면(여기서는 절댓값으로 해줘야 한다. 왜냐하면 음수 노드가 있기 때문이다.) 해당 노드가 음수인지 양수인지를 확인한다. 만일 양수 노드이면 나가는 방향이라는 뜻이기에 정답을 하나 올려준다. 그리고 해당 노드부터 깊이 우선 탐색을 다시 시작한다(여기서도 visit과 마찬가지로 절댓값으로 노드를 넣어줘야 한다).

코드

Java

import java.util.*;
import java.io.*;

class Solution {
    public static List<ArrayList<Integer>> map;
    public static boolean[] visit;
    public static int answer;

    public int minReorder(int n, int[][] connections) {
        map = new ArrayList<>();
        visit = new boolean[n];
        answer = 0;

        for(int i=0; i<n; i++){
            map.add(new ArrayList<>());
        }

        for(int[] connection : connections){
            int a = connection[0];
            int b = connection[1];

            map.get(a).add(b);
            map.get(b).add(-a);
        }

        dfs(0);

        return answer;
    }

    public void dfs(int node){

        visit[node] = true;

        for(int n : map.get(node)){
            if(visit[Math.abs(n)] == false){
                if(n >= 0){
                    answer++;
                }             
                dfs(Math.abs(n));

            }
        }

    }

}

Python

전역변수와 지역변수 때문에 곤란했다. 그래서 그냥 다른 사람이 풀이한 것처럼 dfs 안에 변수를 넣어줬다.

class Solution:

    def minReorder(self, n: int, connections: List[List[int]]) -> int:

        map = [[] for _ in range(n)]
        visit = [False for _ in range(n)]

        for connection in connections:
            a = connection[0]
            b = connection[1]

            map[a].append(b)
            map[b].append(-a)


        def dfs(node: int):
            visit[node] = True
            answer = 0

            for n in map[node]:
                if visit[abs(n)] == False:
                    if n >= 0:
                        answer += 1
                    answer += dfs(abs(n))
            
            return answer

        return dfs(0)