[LeetCode] Keys and Rooms

https://leetcode.com/problems/keys-and-rooms/description/

 

문제 파악

-0번 room부터 순회하며 key를 획득하고, 얻은 키를 가지고 방을 순회. 순회하지 못한 방이 하나라도 있다면 return false.

• n == rooms.length
• 2 <= n <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < n
• All the values of rooms[i] are unique.

 

접근 방법(첫번째 시도)

💡 -방 하나 당 우선 key를 획득하고, 그 다음 차례대로 방을 넘어가므로 bfs를 이용해 풀이

-주어진 리스트를 해시맵 형태로 변환하고 bfs 함수를 만들어 순회한다.

-0은 시작할 때 방문을 열어주는 것과 같으므로, 조건문을 통해 visited에 기본적으로 집어넣는다.

 

접근 방법(개선 사항)

💡 -방 하나 당 우선 key를 획득하고, 그 다음 차례대로 방을 넘어가므로 bfs를 이용해 풀이 -별도로 뺐던 함수 합치기

-주어진 리스트 그대로 사용(해시맵으로 바꿀 필요X)

-visited.add(0) (조건문 필요X)

-방문한 방의 수가 rooms의 수와 같아지면 즉시 true를 반환(불필요한 탐색 줄이기)

-리턴 시, 같으면 return, 다르면 false 리턴되도록 조건문 넣기(==)

 

코드 구현(개선 사항)

• 실행시간 : 2ms

import java.util.*;
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);
        visited.add(0);
        while(!queue.isEmpty()){
            int key=queue.poll();
            for(int v : rooms.get(key)){
                if(!visited.contains(v)){
                    visited.add(v);
                    queue.add(v);
                    if (visited.size() == rooms.size()) {
                        return true;
                    }
                }
            }
        }
        return visited.size() == rooms.size();
    }
}

코드 구현(첫번째 시도)

• 코드 보기
  • 실행 시간 : 7ms

  import java.util.*;
  class Solution {
      public boolean canVisitAllRooms(List<List<Integer>> rooms) {
          Map<Integer,List<Integer>> result = new HashMap<>();
          for(int i=0;i<rooms.size();i++){
              result.put(i,rooms.get(i));
          }
          Set<Integer> visited = bfs(result,0);
          System.out.println(visited.toString());
          for(int i=0;i<rooms.size();i++){
              if(!visited.contains(i)) return false;
          }
  
          return true;
      }
      public Set<Integer> bfs(Map<Integer,List<Integer>> result,int start){
          Set<Integer> visited = new HashSet<>();
          Queue<Integer> queue = new ArrayDeque<>();
          queue.add(start);
          
          while(!queue.isEmpty()){
              int key=queue.poll();
              if(key==0) visited.add(0);
              for(int v : result.get(key)){
                  if(!visited.contains(v)){
                      visited.add(v);
                      queue.add(v);
                  }
              }
          }
          return visited;
      }
  }
  

배우게 된 점

• bfs를 사용할지, dfs를 사용할지 혹은 다른 방식을 사용할 지 고민하는 과정이 한번에 되지는 않았지만, 의미가 있었다.
• 실행시간이 7ms가 나왔는데, 풀이한 사람들을 보니 스택, dfs를 이용해서 푸는 경우도 많았다.
• 좀 더 효율적인 수행을 위해 개선 사항을 생각해보다가 불필요한 구문들을 삭제, 대체하니 성능이 2ms로 크게 향상하였다.