[python3] 1557. Minimum Number of Vertices to Reach All Nodes

풀이 일자: 23.05.18

난이도: [Medium]

분류: [Graph]

문제 내용

문제의 내용은 0 ~ N-1까지의 노드가 있는 순환이 없는 graph가 주어졌을 때 모든 노드에 접근하는 것이 목표이다. 최소한의 시작점을 사용하여 위와 같은 목표를 달성할 때 그 때의 시작점들의 집합을 리턴하는 것이 목표이다.

 

문제 해결 흐름

 

1. 처음에는 Union-Find를 생각해보았지만 그래프가 방향성이 있는 그래프이고 모두 합쳐져 있어서 부적합하다.

→ Union-Find는 Pass

 

2. 그래프를 직접 순회해가면서 각 노드가 접근할 수 있는 노드들의 집합을 구하는 것이 어떨까?

→ 가능은 하지만 시간이 오래 걸릴 것이다. 이는 cycle이 존재할 수 있어 이에 대한 처리가 필요하고 각 시작점에서 접근가능한 노드가 겹칠 수 있어 비효율적으로 보인다.

 

3. Hint를 참조했을 때 income 노드의 여부를 확인하라는 idea가 있었다.

→ 생각해보니 매우 합리적인 idea였다. 화살표의 대상이 되는 노드의 경우 어쨌든 다른 노드를 통해서 접근이 가능하기 때문에 화살표의 대상이 되지 않는 노드 즉 다른 노드에서 접근하지 않는 노드만 count하면 되겠다.

 

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        income = set();
        for i in range(len(edges)):
            income.add(edges[i][1]);
        
        ans = list();
        for i in range(n):
            if i not in income:
                ans.append(i);
        

        return ans;

 

Time Complexity:  O(N+E)

각각 edge와 node에 대해 순회를 돌리기 때문에 edge와 node의 최대값이 Time Complexity가 될 것이다.

 

Space Complexity: O(N)

화살표의 대상이 되는 노드를 income에 저장하고 그 이외의 값을 ans에 저장하기 때문에 공간복잡도는 N이 될 것이다.

 

 

다른 해결 방식

1. 내 풀이보다 좀 더 심플한 방법을 사용한다면(다른 사람 풀이)

→ set에서의 차집합 개념을 이용하여 단순하게 만들었다.

class Solution:
    def findSmallestSetOfVertices(self, n, edges):

        all_nodes = set(range(n))
        destination_nodes = set(destination for _, destination in edges)
        source_nodes = all_nodes - destination_nodes
        
        return list(source_nodes)

 

 

2. BFS를 이용한 풀이도 존재하였다.(다른 사람 풀이)

→ 기존의 BFS 알고리즘을 이용하여  순회를 하는 방식이다.

from collections import defaultdict

class Solution(object):
    def __init__(self):
        self.graph = defaultdict(list)
        self.visited = list()
        self.res = set()
        
    def findSmallestSetOfVertices(self, n, edges):
        self.visited = [False for i in range(n)]
        for u, v in edges:
            self.graph[u].append(v)
            
        for i in range(n):
            if not self.visited[i]:
                self.dfs(i)
                self.res.add(i)   # 현재 노드를 시작점으로 추가
                
        return list(self.res)
    
    def dfs(self, idx):
        self.visited[idx] = True
        for adj in self.graph[idx]:
            if not self.visited[adj]:  # 방문한 적이 없다면 해당 노드에서 dfs 시작
                self.dfs(adj)
            elif adj in self.res:   # 앞으로 방문해야 하는 node가 시작점에 포함되어 있다면 삭제
                self.res.remove(adj)

 

문제 링크

https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/

Minimum Number of Vertices to Reach All Nodes - LeetCode