53. Find if Path Exists in Graph(BFS, DFS)

문제

n개의 노드를 갖는 양방향 그래프가 있다.

각 노드는 0부터 n-1 사이 값을 갖는다.

모든 노드는 최소 하나의 다른 노드와 연결된다.

 

source 노드에서 destination으로 가는 것이 가능하다면 true,

불가능하다면 false를 반환하시오. 

해결 1. BFS

1) 각 node에 연결된 node를 리스트로 정리

2) 큐에 source 노드 삽입

3) visited에 source 노드 삽입

4) 큐에 남아있는 것이 없을 때 까지 popleft

    - popleft한 것이 destination과 일치하면 true

    - popleft한 것이 destination과 일치하지 않으면 큐와 visited에 노드 삽입

5) 큐의 노드를 다 꺼냈는데도 true가 안 나왔으면 false 

from collections import defaultdict, deque

def validPath(n, edges, destination, source):
    neighbors = defaultdict(list)
    # 기본값이 빈 리스트인 딕셔너리 생성

    for node1, node2 in edges:
        neighbors[node1].append(node2)
        neighbors[node2].append(node1)

    queue = deque([destination]) 
    visited = set([destination]) 

    while queue:
        current_node = queue.popleft()
        if current_node == destination:
            return True 
        for node in neighbors[current_node]:
            if node not in visited:
                queue.append(node)
                visited.add(node)

 

예1. True가 나오는 경우

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true

from collections import defaultdict, deque

def validPath(n, edges, destination, source):
    neighbors = defaultdict(list)
    # 기본값이 빈 리스트인 딕셔너리 생성

    for node1, node2 in edges:
        neighbors[node1].append(node2)
        neighbors[node2].append(node1)

    '''
    # neighbors = {
        0 : [1, 2],
        1 : [0, 2],
        2 : [1, 0]
    }
    '''

    queue = deque([destination]) # [0]
    visited = set([destination]) # [0]

    while queue:
        current_node = queue.popleft()
        if current_node == destination:
            return True 
        for node in neighbors[current_node]:
            if node not in visited:
                queue.append(node)
                visited.add(node)

 

예2. False가 나오는 경우

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false

from collections import defaultdict, deque

def validPath(n, edges, destination, source):
    neighbors = defaultdict(list)
    # 기본값이 빈 리스트인 딕셔너리 생성

    for node1, node2 in edges:
        neighbors[node1].append(node2)
        neighbors[node2].append(node1)

    '''
    # neighbors = {
        0 : [1, 2],
        1 : [0],
        2 : [0],
        3 : [4, 5],
        4 : [3, 5],
        5 : [3, 4]
    }
    '''

    queue = deque([destination]) # [0]
    visited = set([destination]) # [0]

    while queue:
        current_node = queue.popleft()
        if current_node == destination:
            return True 
        for node in neighbors[current_node]:
            if node not in visited:
                queue.append(node)
                visited.add(node)

해결 2. DFS

1) 각 node에 연결된 node를 리스트로 정리

2) dfs(node, end, visited) 호출

from collections import defaultdict

def validPath(n, edges, destination, source):
    neighbors = defaultdict(list)
    # 기본값이 빈 리스트인 딕셔너리 생성

    for node1, node2 in edges:
        neighbors[node1].append(node2)
        neighbors[node2].append(node1)

    def dfs(current_node, end, visited):
        if current_node == end:
            return True 
        
        if current_node in visited:
            return False 
		
        visited.add(current_node)
        
        for node in neighbors[current_node]:
            if dfs(node, end, visited):
                return True 

        return False 

    visited = set()
    return dfs(source, destination, visited)