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

문제

• 입력 조건:
  • 정점(vertex) 수가 nnn인 무방향 그래프가 주어집니다. 각 정점은 0부터 n−1n-1n−1까지의 레이블을 가지고 있습니다.
  • 그래프의 간선(edge)은 2차원 정수 배열 edges로 주어집니다. edges[i] = [ui, vi]는 정점 ui와 정점 vi 사이에 양방향 간선이 있음을 나타냅니다.
  • 그래프의 각 정점 쌍은 최대 하나의 간선으로 연결되어 있으며, 자기 자신에게 연결된 간선은 없습니다.
• 문제:
  • 주어진 source 정점에서 destination 정점으로 가는 유효한 경로가 존재하는지 판단하고, 존재한다면 true, 존재하지 않는다면 false를 반환합니다.
• 출력:
  • 만약 source 정점에서 destination 정점까지 가는 경로가 존재하면 true, 그렇지 않으면 false를 반환합니다.

이 문제를 해결하기 위해서는 그래프를 탐색하는 알고리즘(예: DFS 또는 BFS)을 사용하여 source 정점에서 출발하여 destination 정점에 도달할 수 있는지 확인하면 됩니다.

---

문제 해결

• 그래프 생성: 간선 리스트 edges를 이용하여 인접 리스트 형태의 그래프를 생성합니다.
• BFS 큐 초기화: 큐를 생성하고, 시작점인 source를 큐에 넣습니다. 방문한 정점을 추적하기 위해 visited 집합을 사용합니다.
• BFS 실행: 큐에서 정점을 꺼내서 목적지 destination에 도달했는지 확인합니다. 만약 도달했으면 true를 반환합니다. 그렇지 않으면 해당 정점과 연결된 인접 정점을 큐에 추가합니다.
• 결과 반환: BFS가 종료될 때까지 목적지에 도달하지 못하면 false를 반환합니다.

나의 풀이

class Solution {
    
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        // 그래프를 인접 리스트로 표현
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for(int i = 0; i < n; i++){
            graph.put(i, 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<>();
        Set<Integer> visited = new HashSet<>();

        // 시작점(source)에서 시작
        queue.offer(source);
        visited.add(source);
        
        // BFS 수행
        while(!queue.isEmpty()){
            int current = queue.poll();
            // 목적지(destination)에 도달했으면 true 반환
            if(current == destination){
                return true;
            }

            // 현재 노드와 연결된 모든 인접 노드를 탐색
            for(int neighbor : graph.get(current)){
                if(!visited.contains(neighbor)){
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }

        // BFS가 종료될 때까지 목적지에 도달하지 못하면 false 반환
        return false;
    }

}

---