[릿코드 1466] Reorder Routes to Make All Paths Lead to the City Zero(파이썬/python)

https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/description/

Reorder Routes to Make All Paths Lead to the City Zero - LeetCode

 

 

각 노드로 가는 간선이 1개뿐이며(0빼고)

 

0에서 부터 시작돼서 퍼져나가는 형태이기때문에 0부터 시작하는 bfs 를 사용하였습니다.

 

만약 0->1 방향일때 문제에서 요구하는 1 에서 0을 갈 수 없으면 방향을 바꿔야하고

그때마다 answer 변수 값을 1씩 늘려줬습니다.

 

from collections import deque
from typing import List


class Solution:
    def __init__(self):
        self.answer = 0

    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        connection_list = [[] for _ in range(n)]

        for connection in connections:
            start, end = connection
            connection_list[start].append([end, True])
            connection_list[end].append([start, False])

        self.bfs(n, connection_list)

        return self.answer

    def bfs(self, n: int, connection_dic):
        visit = [False for _ in range(n)]
        visit[0] = True
        q = deque()

        for connection in connection_dic[0]:
            q.append(connection)

        while len(q) > 0:
            destination, is_direction = q.popleft()

            if not visit[destination]:
                visit[destination] = True
                if is_direction:
                    self.answer += 1
                for connection in connection_dic[destination]:
                    q.append(connection)