99클럽 코테 스터디 25일차 TIL - 그래프 (LeetCode 1971번)

항해99 코테 스터디 25일차 문제인 리트코드의 1971번 문제는 그래프가 주어졌을 때 시작점에서 도착점까지 도달 가능한지를 판별하는 문제다. 난이도는 쉬움이며 그래프 탐색을 통해 해결할 수 있다.

 

오늘의 문제 - 1971.  Find if Path Exists in Graph 문제 정보

문제 키워드

- 그래프

난이도

- Easy

 

문제 요약

• n개(0~n-1번)의 정점으로 이루어진 양방향 그래프가 있다.
• 간선은 정수 배열 edges[i] = [ui, vi]로 주어진다. (ui ↔ vi는 양방향)
  • 두 정점을 잇는 간선은 최대 1개이며, 자기 자신을 잇는 간선은 존재하지 않는다.
• source부터 destination까지 가는 경로가 존재하는지 여부를 구하여라.

 

문제 풀이 과정  

•  

• 엣지 정보를 연결정보 맵으로 바꾸고, 이 정보를 이용해 시작점부터 그래프 탐색을 수행한다.
• 나는 BFS를 하기 위해 visited 집합 및 Queue를 선언하였다. BFS 과정에서 목적지 노드에 방문하는 경우 true를, 탐색이 끝날 때까지 방문하지 못했다면 false를 반환하였다.

 

코드

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        // 목적지가 출발노드라면 바로 true 반환하고 종료
        if (source == destination) return true;

        // 한 정점과 이어진 다른 정점들의 리스트를 담는 Map
        Map<Integer, List<Integer>> connections = new HashMap<>();
        
        // 정점 연결정보 구하기
        for(int[] edge: edges) {
            int u = edge[0], v = edge[1];

            connections.putIfAbsent(u, new ArrayList<>());
            connections.putIfAbsent(v, new ArrayList<>());

            connections.get(u).add(v);
            connections.get(v).add(u);
        }

        // BFS를 위한 방문정보 집합 및 큐
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();

        // 시작점 넣고 BFS 시작
        visited.add(source);
        q.add(source);

        while(!q.isEmpty()) {
            int here = q.poll();

            for(int next: connections.getOrDefault(here, new ArrayList<>())) {
                // 다음 노드가 목적지라면 true 반환하고 종료
                if (next == destination) {
                    return true;
                }

                // 현재 노드에 연결된 아직 방문하지 않은 정점 방문하기
                if (!visited.contains(next)) {
                    visited.add(next);
                    q.add(next);
                }
            }
        }

        // 목적지를 방문하지 못했으므로 false 반환
        return false;
    }
}

• 시간복잡도: O(n+e) → e: 엣지 개수
• 공간복잡도: O(n+e)

 

오늘의 학습 회고

시간을 더 줄여보려고 목적지 판별을 here 노드가 아닌 next 노드에서 해주었는데, 시간은 비슷하고 오히려 메모리가 줄었다. 아마 탐색을 덜 수행하면서 set과 queue에 값이 덜 들어가서 그런 것 같다.