•
문제 설명 : 제공되는 그래프 정보를 사용하여, 두 지점이 같은 그래프에 존재하는지 확인
•
풀이 방법
◦
union find라는 그래프 알고리즘으로, 두 노드가 동일한 그래프에 존재하는지 판별하는 알고리즘이다.
◦
우선 양방향이기 때문에, 제공된 정보로 각 노드가 어떤 노드와 연결되었는지 확인한다.
◦
기본적인 조건은 2가지이다.
▪
source에서 탐색을 시작 → destination을 찾는다면, 동일 그래프로 True
▪
이미 확인한 노드를 탐색한다면 → False
▪
최종적으로 모든 노드를 확인했음에도, True를 반환하지 못한다면 False 반환
•
시간복잡도 : → 정확하게는 O(V + E) → 모든 노드와 간선을 탐색
◦
이는 하나의 노드에서 여러 간선을 탐색할 수 있다는 의미
◦
이미 방문했던 곳도 결국에는 False를 반환하기 위해 실제 탐색은 하기 때문
•
성공 코드 (DFS)
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# 양방향 그래프 정보 설정
info = defaultdict(list)
for parent, child in edges:
info[parent].append(child)
info[child].append(parent)
# DFS 방식
def dfs(edge, visit):
# 발견하면 True
if edge == destination:
return True
# 이미 탐색한 노드라면 False
if edge in visit:
return False
# 현재 노드 탐색 처리
visit.add(edge)
# 현 노드와 연결된 다른노드 탐색
for next_edge in info[edge]:
# destination을 발견한 경우 True를 반환하여 재귀 순차적 종료
# False는 그냥 넘겨서 다른 노드를 탐색
if dfs(next_edge, visit):
return True
# 현재 하위 탐색을 모두 끝냈음에도 destination을 못찾는다면 False
return False
return dfs(source, set())
Python
복사
•
실패 코드(BFS/시간 초과)
조건은 동일하지만, 큐를 사용한 BFS 방식이다.
시간 초과가 발생하여, 실제 Solved는 못하였다.
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
info = defaultdict(list)
for parent, child in edges:
info[parent].append(child)
info[child].append(parent)
queue = deque()
queue.append(source)
visit = set()
visit.add(source)
while queue:
num = queue.popleft()
visit.add(num)
if num == destination:
return True
for next_edge in info[num]:
if next_edge not in visit:
queue.append(next_edge)
return False
Python
복사
•
성공 코드(BFS)
destination도 결국엔 특정 그래프에 속한다는 아이디어에서 나온 방법이다.
source에서 시작하는 큐와 destination에서 시작하는 큐를 따로 만들어, BFS를 따로 진행하는 방식이다.
다만, 기존 문제의 True 반환 조건과는 다르다.
◦
기존 : [source가 destination를 찾음] or [destination가 source를 찾음] 방식
◦
변경 : [source가 destination에서 시작된 탐색의 방문 노드에 속하는지] or [destination가 source에서 시작된 탐색의 방문 노드에 속하는지] 이다.
▪
즉, 서로 다른 그래프가 아니라면 탐색 중 각자의 탐색 영역에도 속할 것 이라는 아이디어이다.
◦
양쪽에서 탐색을 진행하다보니, 이론상 기존 BFS보다 최대 50% 빠르며 DFS를 사용한 방식보다 더 빨랐다.
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
info = defaultdict(list)
for parent, child in edges:
info[parent].append(child)
info[child].append(parent)
forward_queue = deque([source])
back_queue = deque([destination])
forward_visit = {source}
back_visit = {destination}
while forward_queue and back_queue:
if forward_queue:
num = forward_queue.popleft()
forward_visit.add(num)
if num in back_visit:
return True
for next_edge in info[num]:
if next_edge not in forward_visit:
forward_queue.append(next_edge)
if back_queue:
num = back_queue.popleft()
back_visit.add(num)
if num in forward_visit:
return True
for next_edge in info[num]:
if next_edge not in back_visit:
back_queue.append(next_edge)
return False
Python
복사