[Python] LeetCode - 841. Keys and Rooms

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

Keys and Rooms - LeetCode

 

문제

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

 

0부터 n-1까지의 번호가 있는 방이 있고, 0을 제외한 나머지 방은 모두 잠겨있다. 모든 방을 여는 것이 목표이지만 이 방들은 열쇠없이는 열 수가 없다.

방에 들어가면 열쇠들이 있고, 각 열쇠에는 다른 방을 열 수 있도록 번호가 있다.

 

주어진 rooms 배열의 rooms[i]에는 i번째 방에 있는 열쇠들의 번호들이 있다. 이 때 모든 방을 열 수 있으면 true, 모든 방을 열 수 없으면 false를 return하도록 프로그램을 작성하라.

 

예제 입력 1

rooms = [[1],[2],[3],[]]

 

예제 출력 1

true

Explanation:
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

 

풀이

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = [False for _ in range(len(rooms))]
        stack = [0]
        cnt = 1
        visited[0] = True
        
        while stack:
            keys = rooms[stack.pop()]
            for k in keys:
                if not visited[k]:
                    stack.append(k)
                    visited[k] = True
                    cnt+=1         
                    
        return len(rooms) == cnt

DFS를 이용해서 푼 풀이이다. 방문 여부를 저장하는 visited배열을 방의 갯수(len(rooms))만큼 False로 초기화 해주고, 처음에는 0번 방부터 시작하므로 stack에는 0, cnt에는 1을 넣어주고, visited[0]은 True로 바꿔준다.

 

stack에 값이 있을 경우 아래의 과정을 반복한다.

1. 현재 방문하는 방(stack.pop())에 있는 열쇠들(rooms[stack.pop()])을 for문을 돌면서 각각 확인해준다.

2. 각 열쇠의 방을 방문하지 않았다면 스택에 방의 번호를 append해주고, 방문 처리를 해준다.

 

방문할 수 있는 방을 모두 방문했다면 rooms의 길이와 방문한 방의 갯수(cnt)를 비교한 값을 return해주면 된다.

 

끄읏