[LeetCode] 841. Keys and Rooms

문제링크

0부터 n-1개의 방이 있고, 해당 방에는 다른 방을 열 수 있는 열쇠의 리스트가 주어질 때, 모든 방을 다 열 수 있는지를 확인하는 문제이다. 0번째 방을 제외한 방들은 모두 잠겨있는 상태이다.

재귀를 이용하면 문제를 해결할 수 있다.

예를 들어 0부터 3까지의 방이 있고, 각각의 방에 [[1, 3], [3, 0, 1], [2], [0]]와 같이 열쇠가 있다고 할 때,

0번 방은 열려 있으므로 우선 0은 열 수 있다고 표시해 둔다.

0	1	2	3
T	F	F	F

0번 방에 들어가서 1번 방과 3번 방을 열 수 있는 열쇠를 줍는다.
우선 1번 방에 먼저 들어가자

0	1	2	3
T	T	F	F

1번 방에 들어가서 3번 방, 0번 방, 1번 방을 열 수 있는 열쇠를 줍는다.
3번 방은 아직 들어가지 않았고, 0번 방과 1번 방은 이미 방문했으므로 3번 방에 들어가자

0	1	2	3
T	T	F	T

3번 방에 들어가서 0번 방에 들어갈 수 있는 열쇠를 줍는다.

그렇지만 0번 방은 이미 방문하였고, 0번 방에서 주운 3번 방의 열쇠도 필요가 없으므로 탐색을 종료한다. 탐색을 종료한 상황에서 2번 방은 방문하지 못했으므로 False를 반환한다.

이를 코드로 표현하면 아래와 같다.

class Solution {
public:
    bool opened[1000];
    vector<vector<int>> roomlist;

    void openroom(vector<int> room)
    {
        for(int i=0;i<room.size();i++)
        {
            if(!opened[room[i]])
            {
                opened[room[i]]=true;
                openroom(roomlist[room[i]]);
            }
        }
    }

    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        
        memset(opened, 0, sizeof(opened));

        for(int i=0;i<rooms.size();i++)
        {
            vector<int> keys;

            for(int j=0;j<rooms[i].size();j++)
            {                
                keys.push_back(rooms[i][j]);
            }

            roomlist.push_back(keys);
        }

        opened[0] = true;

        openroom(rooms[0]);  

        for(int i=0;i<rooms.size();i++)
        {
            if(!opened[i]) return false;
        }

        return true;
    }
};