[LeetCode] 841. Keys and Rooms

Luna Park·2022년 12월 20일
0
post-thumbnail

문제링크

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

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

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

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

0123
TFFF

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

0123
TTFF

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

0123
TTFT

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;
    }
};
profile
Happy Ending Is Mine

0개의 댓글