[99클럽 코테 스터디 17일차 TIL] 그래프

📖 오늘의 학습 키워드
그래프

오늘의 회고

문제

[Find if Path Exists in Graph]
https://leetcode.com/problems/find-if-path-exists-in-graph/description/

나의 해결

import java.util.*;
class Solution {
    public boolean[] visited;
    public Map<Integer, List<Integer>> map;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        visited = new boolean[n];
        map = new HashMap<>();
        for(int[] edge : edges) {
            map.computeIfAbsent(edge[0], k -> new ArrayList<Integer>()).add(edge[1]);
            map.computeIfAbsent(edge[1], k -> new ArrayList<Integer>()).add(edge[0]);
        }
        return bfs(n, edges, source, destination);
    }
    public boolean bfs(int n, int[][] edges, int source, int destination) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(source);
        visited[source] = true;
        while(!q.isEmpty()) {
            int now = q.poll();
            if(now == destination) {
                return true;
            }
            for(int vertex : map.get(now)) {
                if(!visited[vertex]){
                    q.offer(vertex);
                    visited[vertex] = true;
                }
            }
        }
        return false;
    }
}

1. 정점의 번호를 key 값으로 갖고 value로 해당 정점의 인접 정점의 번호를 담은 list를 갖는 map을 생성한다.
2. 정점 방문 정보를 기록하는 boolean 배열 visited를 생성한다.
3. edges 배열을 순회하며 정점 간 연결 정보를 저장한다.
4. bfs를 이용해 source로 destination으로 갈 수 있는 경로가 존재하는지 확인한다.
   1) 큐를 생성한다.
   2) source를 큐에 삽입하고 해당 정점을 방문 처리한다.
   3) 큐에서 정점을 꺼내 해당 정점의 인접 정점 중에서 방문하지 않은 정점을 모두 큐에 삽입하고 방문 처리한다.
   4) 큐에서 꺼낸 정점이 destination과 같으면 true를 반환한다.
   5) 더 이상 수행할 수 없을 때까지 위 과정을 반복하고 끝까지 destination을 큐에서 찾을 수 없다면 false를 반환한다.