[리트코드][JAVA] 1971. Find-if-path-exists-in-graph(그래프에 경로가 존재하는지 찾기)

💡 문제
Find-if-path-exists-in-graph (https://leetcode.com/problems/find-if-path-exists-in-graph/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

---

🤓 문제 풀이

🔨 문제 설명

주어진 양방향 그래프에서 n개의 정점이 있습니다. 각 정점은 0부터 n-1까지 번호가 매겨져 있으며, edges라는 2차원 정수 배열로 간선들이 표현됩니다. 여기서 각 edges[i] = [ui, vi]는 정점 ui와 vi 사이에 양방향 간선이 존재함을 나타냅니다. 모든 간선은 두 정점을 최대 한 번 연결하며, 자기 자신에 대한 간선은 없습니다.

우리의 목표는 source에서 시작하여 destination으로 가는 유효한 경로가 있는지를 판단하는 것입니다. edges와 정수 n, 그리고 source와 destination이 주어질 때, source에서 destination으로 가는 유효한 경로가 있는 경우 true를 반환하고, 그렇지 않으면 false를 반환합니다.

예시:

• 입력: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 출력: true 설명: 정점 0에서 2로 가는 경로는 두 가지가 있습니다: 0 → 1 → 2 또는 0 → 2
• 입력: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 출력: false 설명: 정점 0에서 5로 가는 경로가 존재하지 않습니다.

 

해당 문제는 그래프에서 두 정점 사이에 경로가 있는지를 판별하는 문제입니다. 주어진 그래프는 양방향 그래프로, 각 정점은 0부터 n-1까지 번호가 매겨져 있고, edges 배열은 간선들을 나타냅니다. edges 배열의 각 요소는 [ui, vi] 형태로 주어지며, ui와 vi 사이에 양방향 간선이 존재함을 의미합니다. 

---

🔨 접근 방법

1. 그래프 표현: 주어진 edges 배열을 사용하여 인접 리스트 형태로 그래프를 표현합니다. 각 정점에서 연결된 다른 정점들을 리스트로 저장합니다.
2. BFS 탐색: Breadth-First Search (너비 우선 탐색)을 사용하여 source에서 destination으로 가는 경로를 탐색합니다.
   • BFS는 시작 정점에서 가까운 정점부터 탐색하며, 최단 경로를 찾는 데 유리합니다.
   • 방문한 정점을 표시하기 위해 boolean 배열 visited를 사용합니다.
3. 결과 반환: BFS 탐색을 마친 후 destination을 방문했는지 여부에 따라 true 또는 false를 반환합니다.

---

🔨 문제 풀이 과정

• 특수 케이스 처리: 코드는 먼저 시작 정점 source와 목표 정점 destination이 동일한지 확인합니다. 이 경우에는 바로 true를 반환하여 함수를 종료합니다. 이는 시작과 도착이 같은 경우에는 항상 경로가 존재한다는 것을 의미합니다.
• 그래프 표현: 인접 리스트를 사용하여 그래프를 표현합니다. 이 때, 주어진 edges 배열을 이용하여 각 정점에서 직접 연결된 정점들을 리스트로 저장합니다.
• BFS 탐색: 너비 우선 탐색(BFS)을 사용하여 시작 정점 source에서 목표 정점 destination까지의 경로 유무를 확인합니다. BFS는 큐(Queue) 자료구조를 사용하여 레벨 순서대로 탐색하며, 가장 짧은 경로를 찾는 것이 가능합니다.
• 방문 여부 표시: 탐색 중 방문한 정점은 visited 배열을 통해 표시하여 중복 방문을 방지합니다. 이는 무한 루프를 피하고 효율적인 탐색을 보장합니다.
• 결과 반환: BFS 탐색을 마치고 목표 정점 destination에 도달할 수 있는지 여부에 따라 true 또는 false를 반환합니다. 도달할 수 없는 경우를 처리하기 위해 BFS가 끝난 후에도 목표 정점을 방문하지 못했으면 false를 반환합니다.

---

🔨 알고리즘 선택 이유

래프 탐색을 선택하는 이유는 다양한 문제 상황에서 탐색의 필요성과 효율성 때문입니다. 그래프는 정점(vertex)과 간선(edge)으로 이루어진 자료 구조

1. 경로 탐색: 특정 정점에서 다른 정점까지의 경로가 존재하는지, 혹은 최단 경로를 찾는 문제는 그래프 탐색 알고리즘을 사용하여 해결할 수 있습니다. 너비 우선 탐색(BFS)은 최단 경로를 찾는 데 유리하며, 깊이 우선 탐색(DFS)은 경로의 존재 여부를 판단할 때 유용합니다.
2. 연결성 검사: 그래프 내에서 모든 정점이 서로 연결되어 있는지 검사하는 문제도 그래프 탐색으로 해결할 수 있습니다. DFS나 BFS를 통해 시작 정점에서 도달 가능한 모든 정점을 탐색하고, 모든 정점을 방문했는지 여부로 연결성을 판단할 수 있습니다.
3. 사이클 탐지: 그래프에 사이클이 존재하는지 여부를 판단할 때도 DFS를 사용합니다. 사이클이 존재하는 경우, 같은 정점을 두 번 방문하는 경로가 존재하게 되어 사이클을 감지할 수 있습니다.
4. 최소 스패닝 트리: 최소 스패닝 트리(Minimum Spanning Tree, MST) 문제는 그래프의 모든 정점을 가장 적은 비용으로 연결하는 문제로, 프림(Prim) 알고리즘이나 크루스칼(Kruskal) 알고리즘과 같은 그래프 탐색 기반의 알고리즘이 사용됩니다.

이처럼 다양한 문제에서 그래프 탐색은 필수적인 요소로 작용하며, 특히 BFS와 DFS는 간단하면서도 강력한 탐색 방법으로서 널리 사용됩니다. 선택하는 탐색 방법은 문제의 특성에 따라 달라질 수 있으며, 경로의 길이가 중요한 경우 BFS를, 모든 가능성을 탐색해야 할 때는 DFS를 선호할 수 있습니다.

---

🔨 구현코드

import java.util.*;

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) {
            return true; // source와 destination이 같으면 항상 true를 반환
        }
        
        // 그래프의 인접 리스트 생성
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 간선 정보를 바탕으로 인접 리스트 채우기
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            graph.get(u).add(v);
            graph.get(v).add(u); // 양방향 그래프이므로 양쪽에 모두 추가
        }
        
        // BFS 준비
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        
        queue.offer(source);
        visited[source] = true;
        
        // BFS 탐색
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            // 현재 정점의 모든 이웃 탐색
            for (int neighbor : graph.get(current)) {
                if (!visited[neighbor]) {
                    if (neighbor == destination) {
                        return true; // 목적지에 도달한 경우 true 반환
                    }
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
        
        // BFS를 마치고도 목적지에 도달하지 못한 경우 false 반환
        return false;
    }
}

---

📚 풀이 보완

코드 설명

• graph: 인접 리스트로 그래프를 표현하기 위한 리스트 배열입니다. 각 정점에 연결된 정점들을 리스트로 저장합니다.
• BFS를 사용하여 source에서 시작하여 destination까지 경로를 탐색합니다.
• queue를 사용하여 BFS를 구현하며, visited 배열을 통해 방문한 정점을 체크합니다.
• BFS 탐색 중에 destination에 도달하면 true를 반환하고, 탐색을 마친 후에도 도달하지 못하면 false를 반환합니다.

---

📍 Plus+

시간 복잡도

BFS는 너비 우선 탐색으로, 최악의 경우 모든 정점과 간선을 탐색해야 할 수 있습니다. 그래프가 인접 리스트로 표현되어 있을 때, BFS의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다.

공간 복잡도

• 인접 리스트: 그래프의 각 정점마다 연결된 정점을 리스트로 저장하는 데 필요한 공간입니다. 주어진 그래프의 간선 수에 따라 O(E)의 공간이 필요합니다. 여기서 E는 간선의 수입니다.
• 큐: BFS를 위해 사용되는 큐의 공간입니다. 최악의 경우 모든 정점이 큐에 들어갈 수 있으므로 O(V)의 공간이 필요합니다. 여기서 V는 정점의 수입니다.
• 방문 여부 배열: 각 정점이 방문되었는지를 체크하는 boolean 배열이 필요합니다. 이 배열은 정점의 수에 따라 O(V)의 공간을 필요로 합니다.

요약

• 시간 복잡도: O(V + E)
• 공간 복잡도: O(V + E)

 

---

풀이 참고 로직