99클럽 코테 스터디 25일차 TIL | Find if Path Exists in Graph

🖥️ 문제

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:

• 0 → 1 → 2
• 0 → 2

📝 풀이

import java.util.*;

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        // 그래프 구성
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        // 각 엣지를 그래프에 추가
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        // 큐, 방문 기록 배열 생성
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        
        // 탐색 시작
        queue.offer(source);
        visited[source] = true;
        
        // 큐가 빌 때까지 탐색
        while (!queue.isEmpty()) {

            //탐색 중인 노드를 큐에서 꺼내고
            int current = queue.poll();
            
            // 현재 노드가 목적지라면 true 반환
            if (current == destination) {
                return true;
            }
            
            // 현재 노드와 연결된 모든 이웃 노드 탐색
            for (int neighbor : graph.get(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // 이웃 노드를 방문 처리
                    queue.offer(neighbor); // 이웃 노드를 큐에 추가
                }
            }
        }
        
        // 목적지에 도달하지 못한 경우 false 반환
        return false;
    }
}

문제의 핵심은 그래프에서 출발지(source)에서 목적지(destination)로 가는 경로가 있는지를 찾는 것이다. 무방향 그래프에서 이 경로가 존재하는지 확인하기 위해 BFS(너비 우선 탐색)를 사용했다.

먼저, 주어진 엣지들을 이용해 그래프를 인접 리스트로 만들었다. 각 노드가 연결된 다른 노드들을 리스트로 관리하는 방식이다. 그런 다음, BFS를 통해 출발지에서 탐색을 시작해 큐를 사용해 노드들을 순차적으로 탐색했다. 현재 노드가 목적지에 도달했다면, 바로 true를 반환했다. 만약 큐가 빌 때까지 목적지에 도달하지 못했다면 false를 반환했다.

👀 고찰

문제를 풀면서 BFS가 경로 탐색에서 얼마나 직관적이고 효과적인지 다시 느꼈다. DFS와 비교해봤을 때, BFS는 너비 우선으로 탐색하므로 경로의 존재 여부를 빠르게 확인할 수 있었다. 특히 이 문제처럼 최단 경로가 아닌 단순히 경로의 존재 여부만 확인할 때는 BFS가 더 적합하다는 생각이 들었다.