Find if Path Exists in Graph
학습 키워드: bfs, dfs, union-find
문제 링크: https://leetcode.com/problems/find-if-path-exists-in-graph/
문제 설명
n개의 정점이 있는 양방향 그래프가 있습니다. 각 정점은 0부터 n-1까지의 레이블이 붙어 있습니다. 그래프의 간선은 2D 정수 배열 edges로 표현되며, 각 edges[i] = [ui, vi]는 정점 ui와 정점 vi 사이의 양방향 간선을 나타냅니다. 각 정점 쌍은 최대 하나의 간선으로 연결되며, 자기 자신과 연결된 간선은 없습니다.
정점 source에서 정점 destination까지 유효한 경로가 존재하는지 여부를 확인하고자 합니다.
주어진 edges와 정수 n, source, destination이 주어질 때, source에서 destination까지 유효한 경로가 있으면 true를, 없으면 false를 반환하세요.
제한 조건
- 1 <= n <= 2 * 105
- 0 <= edges.length <= 2 * 105
- edges[i].length == 2
- 0 <= ui, vi <= n - 1
- ui != vi
문제 풀이
다양하게 풀 수 있는 문제라 다양한 풀이를 적었다. 간선에 가중치가 없기 때문에 dfs,bfs로 풀이를 해도 괜찮다고 생각을 했다.
-dfs(2885 ms)
첫 시도는 dfs로 시작 graph 정보를 초기화 해준 뒤 dfs로 시작 노드에 연결된 노드들을 for문으로 dfs로 들어가면서 도착지점에 도달할 경우 True를 반환하고 다 돌았을 때 도착지점에 도달 못하면 False를 반환하게 한다.
from typing import List
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# dfs로 풀까
graph = [[] for _ in range(n+1)]
visited = [False]*(n+1)
for edge in edges:
st,ed = edge
graph[st].append(ed)
graph[ed].append(st)
def dfs(st):
visited[st]=True
if st == destination:
return True
for node in graph[st]:
if not visited[node]:
if dfs(node):
return True
return False
return dfs(source)-bfs(2481ms)
코드가 안될 때 이리저리 붙여넣기 하다가 시간이 엄청 오래걸려버린 bfs.. 코드 최적화를 위해 defaultdict(list)를 사용해줬다. defaultdict로 특정 노드(key)에 연결된 노드들(List[int])의 리스트를 key값을 초기화하지 않고도 초기화할 수 있다.
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# bfs로 풀까
graph = defaultdict(list)
for a,b in edges:
graph[a].append(b)
graph[b].append(a)
visited = set([source])
queue = deque([source])
while queue:
now = queue.popleft()
if now == destination:
return True
for node in graph[now]:
if node not in visited:
visited.add(node)
queue.append(node)
return False-union/find (2372ms)
union_find (합집합 찾기 알고리즘)으로 root node가 같은지 판별하는 식을 return 했다.
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
parent = list(range(n))
def find(x):
if x != parent[x]:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
parent_a = find(a)
parent_b = find(b)
if parent_a != parent_b:
parent[parent_a] = parent_b
for a, b in edges:
union(a, b)
return find(source) == find(destination)코멘트
처음엔 10분만에 풀었지만.. 하위 10%속도 올리겠다고 여러 경우의 수를 파악하면서 1시간 반을 더 썼다. 평소에는 dfs와 같이 graph와 visited를 초기화하는 방법을 많이 쓰지만 defaultdict와 visited를 set로 선언하는 것도 연습해보았다. 배워도 나중에 응용하기 위해서는 뭐든지 일단 써봐야 한다는 생각
