[99클럽 코테 스터디] 25일차 TIL 그래프

 

 

오늘의 문제는 LeetCode

 

1971. Find if Path Exists in Graph

 

 

문제

 

 

 

문제 설명 

 

주어진 양방향 그래프에서 정점 source에서 destination으로 가는 경로가 존재하면 true를 반환하고, 존재하지 않으면 false를 반환하는 문제입니다. 그래프는 n개의 정점을 가지고 있고 각 정점은 0 부터 n - 1 까지의 번호를 갖습니다. 간선은 2차원 정수 배열 edges로 주어집니다. 

예를 들어 Input : n = 3, edges = [[0,1], [1,2],[2,0]], source = 0, destination = 2 일 때 0에서 2까지 가는 경로가 0 -> 1 -> 2 와 0 -> 2로 존재하므로 output은 true입니다. 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 47분이 걸렸습니다.

 

 

 

 

문제 접근 방식

edges 배열을 순회하며 각 간선에 대해 두 정점 사이의 연결을 인접 리스트에 추가하는 방식으로 그래프를 인접 리스트로 표현합니다.  그 다음 BFS 알고리즘을 사용해 source에서 destination 까지의 경로가 있는지 탐색합니다. 먼저 큐를 사용해 현재 정점과 인접한 정점들을 순차적으로 탐색한 뒤 큐에서 꺼낸 정점이 destination 정점과 일치하는지 확인하고 일치하면 경로가 존재하는 것이기 때문에 true를 반환합니다. 

경로를 전부 탐색했는데도 destination에 도달하지 못했다면 경로가 없다는 것이므로 false를 반환합니다. 

 

 

 

 

 

문제 풀이

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.add(source);
        visited[source] = true;

        while(!queue.isEmpty()) {
            int node = queue.poll();

            if(node == destination) {
                return true;
            }

            for(int neighbor : graph.get(node)) {
                if(!visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                }
            }
        }

        return false; 
    }
}

 

 

1차 시도 : 인접 행렬을 통한 풀이 

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        
        boolean[][] graph = new boolean[n][n];

        for(int[] edge : edges) {
            graph[edge[0]][edge[1]] = true;
            graph[edge[1]][edge[0]] = true;
        }

        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];

        queue.add(source);
        visited[source] = true;

        while(!queue.isEmpty()) {
            int node = queue.poll();

            if(node == destination) {
                return true;
            }

            for(int i = 0; i < n; i++) {
                if(graph[node][i] && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }

        return false; 

    }
}

 

 

인접 행렬을 사용 했을 때의 문제점 

인접 행렬을 사용해 그래프를 구현하면 n = 3000 일 경우 Memory Limit Exceeded 오류가 발생합니다. 

그 이유는 현재 boolean형 2차원 배열 graph로 인접 행렬을 표현하고 있는데 크기를 n x n 으로 설정하였기 때문입니다. 따라서 n이 커질수록 메모리 사용량이 급격히 증가하게 됩니다. 

 

 

 

 

인접 리스트 사용하기

기존 인접 행렬을 통한 구현을 인접 리스트를 사용한 방식으로 변경합니다.

인접 리스트는 간선의 개수에 비례하는 메모리를 사용합니다. 따라서 노드 개수에 따라 메모리 사용량이 기하급수적으로 증가하게 되는 인접 행렬에 비해 메모리 사용량을 많이 줄일 수 있습니다. 

// 변경 전 인접 행렬 사용
boolean[][] graph = new boolean[n][n];
// 변경 후 인접 리스트 사용
List<List<Integer>> graph = new ArrayList<>();

 

 

 

 

 

 

 

 

이렇게 오늘 25일차 TIL을 작성해 보았습니다.