Leetcode - 1971. Find if Path Exists in Graph (그래프)

문제

edge가 주어질때, source -> destination 에대한 경로가 존재하면 true 아니면 false.

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

https://leetcode.com/problems/find-if-path-exists-in-graph/

해결 DFS - 그래프 인접행렬 방법

그래프 엣지를 표현하는 자료구조 생성(2차원배열로 graph map 생성)
이 방법은, 노드가 많은데 연결이 적은 그래프에서 2차원 배열사이즈가 과도하게 크고, 메모리를 많이 차지한다는 단점이있다.

제출해보면, 답은 맞는데 ,22/26 Test Case에서 Memory Limit Exceeded 가 발생.

int *visit;
int **map;
int dest;
int nr;

bool dfs(int **m, int row)
{
    if (row == dest)
        return true;
    if (visit[row])
        return false;
    visit[row] = 1;
    for (int i = 0; i < nr; i++) {
        if (m[row][i] == 1) {
            if (dfs(m, i))
                return true;
        }
    }
    return false;
}

bool validPath(int n, int** edges, int edgesSize, int* edgesColSize, int source, int destination)
{
    bool ret = false;
    dest = destination;
    nr = n;
    map = (int **)calloc(n, sizeof(int *));
    for (int i = 0; i < n; i++)
        map[i] = (int *)calloc(n, sizeof(int *));
    visit = (int *)calloc(n, sizeof(int));
    
    /* generate graph map */
    for (int i = 0; i < edgesSize; i++)
        map[edges[i][0]][edges[i][1]] = map[edges[i][1]][edges[i][0]] = 1;
    
    ret = dfs(map, source);
    for (int i = 0; i < n; i++)
        free(map[i]);
    free(map);
    return ret;
}

해결 DFS - 그래프 인접 리스트 방법

그래프 엣지를 표현하는 자료구조 생성(인접 리스트 방식) 가령, 엣지가 [[0,1],[0,2],[3,5],[5,4],[4,3]] 로 주어질때, 엣지를 표현하는 링크드 리스트는 아래와 같다.

[0] -> 1 -> 2
[1] -> 0
[2] -> 0
[3] -> 4 -> 5
[4] -> 3 -> 5
[5] -> 3 -> 4

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false

링크드 리스트를 생성할때 주의점. 이 그래프는 방향이 없는 그래프 이기 때문에, [a,b] 일때 a->b 그리고 b->a두개를 malloc해서 추가해야한다.

DFS구현은 visit[] 배열이 1로 바뀌느 시점 확인.

struct node {
    int val;
    struct node *next;
};
struct node **map;
bool *visit;

bool dfs(struct node **m, int curr, int dest)
{
    if (curr == dest)
        return true;
    if (visit[curr])
        return false;
    visit[curr] = 1;
    
    struct node *node = m[curr];
    for (;node != NULL; node = node->next)
        if (dfs(m, node->val, dest))
            return true;
    return false;
}

bool validPath(int n, int** edges, int edgesSize, int* edgesColSize, int source, int destination)
{
    map = (struct node **)calloc(n, sizeof(struct node *));
    visit = (bool *)calloc(n, sizeof(bool));
    
    /* generate graph map */
    for (int i = 0; i < edgesSize; i++) {
        // a -> b
        struct node *newnode = (struct node *)malloc(sizeof(struct node));
        newnode->val = edges[i][1];
        newnode->next = map[edges[i][0]];
        map[edges[i][0]] = newnode; 
        // b -> a
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->val = edges[i][0];
        newnode->next = map[edges[i][1]];
        map[edges[i][1]] = newnode; 
    }
    return dfs(map, source, destination);
}