← 15주차 · 그래프와 DFS · BFS
쉬움그래프DFS

경로 존재 판별

정점 개수 n과 간선 목록 edges로 이루어진 무방향 그래프가 주어져요. 정점은 0번부터 n-1번까지 있고, edges의 각 원소 [a, b]는 a와 b를 잇는 길이에요.

출발 정점 start에서 도착 정점 target까지 길을 따라 갈 수 있으면 true, 갈 수 없으면 false를 반환해요.

먼저 간선 목록으로 인접 리스트를 만들고, start에서 DFS나 BFS로 퍼져 나가며 target에 닿는지 확인해요. 방문한 정점을 다시 방문하지 않도록 방문 표시를 꼭 해요.

예시

예시 1
입력
n = 6, edges = [[0, 1], [1, 2], [3, 4]], start = 0, target = 2
출력
true
설명
0 → 1 → 2로 갈 수 있어요.
예시 2
입력
n = 6, edges = [[0, 1], [1, 2], [3, 4]], start = 0, target = 4
출력
false
설명
0이 속한 덩어리와 4가 속한 덩어리가 떨어져 있어요.

제한 사항

  • 1 ≤ n ≤ 100,000
  • 0 ≤ edges.length ≤ 200,000
  • 0 ≤ a, b, start, target < n
  • self-loop나 중복 간선이 있을 수 있어요.
인접 리스트를 만든 뒤 스택(또는 큐)에 start를 넣고 방문 표시해요. 하나씩 꺼내며 target이면 true를 반환하고, 아직 방문하지 않은 이웃을 표시하며 넣어요. 다 훑어도 못 만나면 false예요.
javascript
function pathExists(n, edges, start, target) {
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }
  const visited = new Array(n).fill(false);
  const stack = [start];
  visited[start] = true;
  while (stack.length > 0) {
    const v = stack.pop();
    if (v === target) return true;
    for (const next of graph[v]) {
      if (!visited[next]) {
        visited[next] = true;
        stack.push(next);
      }
    }
  }
  return false;
}
이전 문제이진 탐색 트리 유효성 검사
다음 문제연결 요소의 개수
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.