LeetCode 841. Keys and Rooms (Java)

문제 링크

The problem link : LeetCode 841. Keys and Rooms

문제 요약

1. 0번째부터 n-1까지 라벨이 붙여진 방이 있습니다.
2. 0번째 문을 제외한 나머지 문은 잠겨있습니다.
3. 방에 들어갔을때, 해당 방에 존재하는 key를 사용할 수 있게됩니다. 이렇게되면 key를 사용해 해당 방에 들어갈 수 있습니다.
4. 당신의 목적은 0번째부터 n-1까지의 모든 방을 들어가는 겁니다. 가능할 경우 true를, 그렇지 않을 경우 false를 출력하세요.
   

예시

입력값 : rooms = [[1,3],[3,0,1],[2],[0]]
출력값 : false
해설 : 2번째 방(=[2])에 들어갈 수 없기 때문에 false입니다.

조건

- n == rooms.length - 2 <= n <= 1,000 
- 0 <= rooms[i].length <= 1,000 
- 1 <= sum(rooms[i].length) <= 3,000 
- 0 <= rooms[i][j] < n - rooms[i]에 있는 값들은 동일하지 않고 모두 고유합니다. 

문제 풀이

class Solution { 
    public boolean canVisitAllRooms(List<List> rooms) { 
      if(rooms.size() == 0) return true;
      boolean[] visited = new boolean[rooms.size()];
      Queue<Integer> q = new LinkedList<>();

      for(Integer room : rooms.get(0)){ // 0
          q.offer(room);
      }
      visited[0] = true;

      while(!q.isEmpty()) { // 1
          Integer pos = q.peek();
          if(!visited[pos]) {
              for(Integer temp : rooms.get(pos)) {
                  q.offer(temp);
              }
              visited[pos] = true;
          }
          q.remove();
      }

      for(boolean temp : visited){ // 2
          if(!temp) return false;
      }

      return true;
    }
}

BFS를 활용한 Graph 문제 입니다.

0. rooms[0]에 있는 key를 모두 큐에 저장한 뒤, 0번째 방은 방문했다는 표시를 해줍니다.
1. 큐에 저장된 첫 번째 값(이하 '키')부터 탐색을 시작합니다. 만약 큐에 저장된 첫번째 키에 해당되는 방을 방문한 적이 없다면, 해당 방에 저장된 모든 키를 큐에 저장합니다. 그런 다음, 해당 방을 방문처리 해주고 큐에서 제거합니다.
2. 모든 방에서 한 곳이라도 방문한 적이 없다면 false를, 그렇지 않고 for문을 통과한다면 true를 반환해줍니다.

시간 복잡도

O(N+E)입니다.
(N=room의 개수, E=key(각 room이 가지고있는 key)의 개수)


공간복잡도는 O(N) 입니다.