[LeetCode] 841. Keys and Rooms / JAVA

>> 문제설명

leetcode.com/problems/keys-and-rooms/

Keys and Rooms - LeetCode

> 0개 이상의 간선을 가진 단일 방향 그래프에서 모든 정점을 탐색할 수 있는지를 묻는 문제입니다.

> BFS, DFS 와 같은 그래프 탐색 알고리즘을 사용하여 모든 정점의 방문 여부를 체크합니다.

 

> Solution(BFS)

import java.util.Arrays;
import java.util.List;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        LinkedList<Integer> openList = new LinkedList<>();
        HashSet<Integer> isOpened = new HashSet<>();
        
        isOpened.add(0);
        openList.add(0);

        while (!openList.isEmpty()){
            int size = openList.size();
            for(int i = 0; i < size; i++){
                for(int room : rooms.get(openList.pollFirst())){
                    if(!isOpened.contains(room)){
                        openList.add(room);
                        isOpened.add(room);
                    }
                }
            }
        }

        return isOpened.size() == rooms.size() ? true : false;
    }
}