99클럽 코테 스터디 25일차 - 그래프

문제

풀이

• 인접리스트 후 source부터 destination까지 도달하는지 체크하는 문제
• bfs로 탐색하면 된다.

코드

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        Map<Integer, List<Integer>> graph = new HashMap();
        
        for(int[] e : edges) {
            int from = e[0];
            int to = e[1];
            
            graph.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
            graph.computeIfAbsent(to, k -> new ArrayList<>()).add(from);
        }
        
        boolean[] visited = new boolean[n + 1];
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(source);
        
        visited[source] = true;
        
        while(!queue.isEmpty()) {
            int node = queue.poll();
            
            if(node == destination) return true;
            
            if(graph.containsKey(node)){
                for(int nextNode : graph.get(node)){
                    if(!visited[nextNode]){
                        visited[nextNode] = true;
                        queue.add(nextNode);               
                    }
                }
            }
        }
        
        return false;
    }
}

정리

• path를 생성해서 모든 경로를 저장하려고 했는데 어차피 시작을 source로 지정해서 node에서 destination를 꺼내는지만 확인하면 되었다