-
LeetCode - 841. Keys and Rooms개발/코딩테스트 2023. 8. 25. 14:44
문제: 841. Keys and Rooms (Medium)
1. 0 부터 n-1 까지 표시된 n 개의 방이 있고, 0번 방을 제외한 모든 방은 잠겨 있음. 모든 방을 방문하려 함.
2. 방을 방문하면 열쇠를 찾을 수 있고 숫자는 방의 번호를 나타냄.
2. 모든 방을 방문할 수 있으면 true, 아니면 false 리턴.예시:
Example 1:
Input: rooms = [[1],[2],[3],[]]Output: true
Explanation: 0번째 방에서 1번 방의 열쇠를 얻음. 1번 방에서 2번 방의 열쇠를 얻음. 2번 방에서 3번방의 열쇠를 얻음. 3번방까지 모두 방문 할 수 있으므로 true.
Example 2:
Input: rooms = [[1,3],[3,0,1],[2],[0]]Output: false
Explanation: 2번 방의 열쇠는 2번방에만 있어서 방문할 수 없으므로 false.
풀이:
class Solution { public boolean canVisitAllRooms(List<List<Integer>> rooms) { boolean[] visited = new boolean[rooms.size()]; visited[0] = true; return visit(0, rooms, visited) == rooms.size(); } private int visit(int num, List<List<Integer>> rooms, boolean[] visited) { int sum = 1; for (Integer i : rooms.get(num)) { if (!visited[i]) { visited[i] = true; sum += visit(i, rooms, visited); } } return sum; } }
설명:
1. visitCount 와 방문 여부를 기록할 visited boolean 배열 선언.
2. 첫번째 방부터 재귀적으로 방문하며 방문하지 않은 곳은 visited 를 true 로 기록하고 모두 방문.
3. 최종적으로 visit 에서 리턴되는 값은 방문을 한 count 이며, 해당 count 와 rooms 의 size 를 비교하여 그에 맞게 true, false 리턴.
시간복잡도: O(n)
공간복잡도: O(n)
Runtime: 0ms Beats 100.00% of users with Java
Memory: 43.04MB Beats 76.20% of users with Java
개인의 해답으로 풀이한 문제입니다.
절대적인 정답이 아닐 수 있으며, 더 좋은 개선 방안이 있다면 댓글로 의견 주세요.'개발 > 코딩테스트' 카테고리의 다른 글
LeetCode - 746. Min Cost Climbing Stairs (0) 2023.08.25 LeetCode - 2336. Smallest Number in Infinite Set (Java) (0) 2023.08.24 LeetCode - 2390. Removing Stars From a String (Java) (0) 2023.08.23 LeetCode - 1431. Kids With the Greatest Number of Candies (Java) (0) 2023.08.23 LeetCode - 1768. Merge Strings Alternately (Java) (0) 2023.08.23