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

오늘의 학습 키워드

</> 그래프

공부한 내용 본인의 언어로 정리하기

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

        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            map.put(i, new ArrayList<>());
        }

        for (int[] edge : edges) {
            map.get(edge[0]).add(edge[1]);
            map.get(edge[1]).add(edge[0]);
        }

        return dfs(map, source, destination, new HashSet<>());
    }

    private boolean dfs(Map<Integer, List<Integer>> graph, int current, int destination, Set<Integer> visited) {

        if (current == destination) return true;

        visited.add(current);

        for (int neighbor : graph.get(current)) {

            if(!visited.contains(neighbor)) {
                if(dfs(graph, neighbor, destination, visited))
                    return true;
            }
        }

        return false;
    }
}

오늘의 회고

오늘 문제는 2시간을 넘게 고민을 해보았지만 결과를 낼 수가 없어, AI와 클럽장님의 도움을 받은 풀이로 진행을 한다.
오늘은 그래프에서 특정 노드(source)에서 다른 노드(destination)까지의 경로가 존재하는지를 확인하는 문제를 해결했습니다. 이 문제를 해결하기 위해 다음과 같은 작업을 수행했습니다:

1. 그래프의 인접 리스트 생성

• 주어진 간선 배열(edges)을 사용하여 각 노드와 그 노드에 연결된 다른 노드들을 인접 리스트 형태로 저장했습니다.
• 인접 리스트를 저장하기 위해 HashMap을 사용했습니다. 각 노드가 키가 되고, 그 노드에 연결된 노드들의 리스트가 값이 되도록 했습니다.

2. 깊이 우선 탐색 (DFS) 구현

• DFS를 통해 그래프를 탐색하며, 주어진 source 노드에서 destination 노드까지 도달할 수 있는지 확인했습니다.
• 탐색 중 방문한 노드를 기록하여 무한 루프를 방지했습니다.

Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < n; i++) {
    map.put(i, new ArrayList<>());
}
for (int[] edge : edges) {
    map.get(edge[0]).add(edge[1]);
    map.get(edge[1]).add(edge[0]);
}

그래프의 모든 노드에 대해 빈 리스트를 초기화한 후, 주어진 간선 정보를 통해 각 노드의 인접 리스트를 업데이트했습니다.

private boolean dfs(Map<Integer, List<Integer>> graph, int current, int destination, Set<Integer> visited) {
    if (current == destination) return true;
    visited.add(current);
    for (int neighbor : graph.get(current)) {
        if (!visited.contains(neighbor)) {
            if (dfs(graph, neighbor, destination, visited)) return true;
        }
    }
    return false;
}

• DFS를 통해 현재 노드가 목표 노드와 같은지 확인하고, 목표 노드가 아닌 경우 인접 노드를 탐색합니다.
• 방문한 노드를 기록하여 반복 방문을 방지합니다.

내일 공부할 것 :

아직 이해를 정확히 하지 못했다... 다시 공부해서 재정리 할 필요가 있다.

문제

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