99클럽 코테 스터디 25일차 TIL + 오늘의 학습 키워드

ㅎㅇ·2024년 8월 15일
0

항해99 TIL

목록 보기
19/33
post-custom-banner

*문제

*코드
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]);
    }
    
  
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(source);
    visited[source] = true;
    
    while (!queue.isEmpty()) {
        int current = queue.poll();
        if (current == destination) {
            return true;
        }
        
        for (int neighbor : graph.get(current)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
    
    return false;
}

}

*리뷰
먼저 주어진 edges를 사용하여 인접 리스트 형태의 그래프를 만듭니다.
BFS(너비 우선 탐색)를 사용하여 source에서 시작하여 destination까지의 경로를 찾습니다.
큐를 사용하여 BFS를 구현하고, visited 배열로 이미 방문한 노드를 체크합니다.
destination에 도달하면 true를 반환하고, 모든 연결된 노드를 탐색했는데도 destination에 도달하지 못하면 false를 반환합니다.

profile
안녕하세요
post-custom-banner

0개의 댓글