[C] LeetCode 841. Keys and Rooms

문제

 

번역

 

0번부터 n-1번까지의 번호가 붙은 n개의 방이 있고, 0번 방을 제외한 모든 방은 잠겨있다.

우리의 목표는 모든 방을 방문하는 것이다. 하지만, 너는 열쇠 없이는 방에 들어갈 수 없다.

 

우리가 방에 방문한다면 구별되는 키들의 집합을 찾을 수 있을 것이다(여기에는 공집합이 있을 수 있다, 다시 말해 비어있다.) 각 키의 번호가 각 방을 열 수 있는 열쇠이다.

 

rooms 배열의 i번째 원소는 i번째 방을 방문했을 때 얻을 수 있는 키들이다. 

만약 모든 방을 방문할 수 있다면 true를, 불가능하다면 false를 반환해라.

 

접근 방법 및 소스코드

0번 노드부터 시작하는 DFS/BFS 탐색으로 접근하면 된다.

0번 노드에서 얻은 키는 0번 노드와 연결된 방들이고, 이 키들을 stack/queue 등에 넣어서 최대한 갈 수 있는 모든 방을 방문하고 기록을 남긴다.

이후 내가 방문하지 못한 방이 하나라도 있으면 false를, 그게 아니라면 true를 반환하게 하면 된다.

 

int stack[1002];
int visited[1002];
int rsp;

bool canVisitAllRooms(int** rooms, int roomsSize, int* roomsColSize) {
    rsp = -1;
    memset(stack, 0, sizeof(stack)); memset(visited, 0, sizeof(visited));
    for(int i=0; i<roomsColSize[0]; i++) {
        if(!visited[rooms[0][i]])
            stack[++rsp] = rooms[0][i];
    }
    visited[0]=1;
    while(rsp > -1) {
        if(visited[stack[rsp]] == 1) { rsp--; continue; }
        visited[stack[rsp]] = 1;
        int ptr = stack[rsp--];
        for(int i=0; i<roomsColSize[ptr]; i++) {
            if(!visited[rooms[ptr][i]])
                stack[++rsp] = rooms[ptr][i];
        }
    }

    for(int i=0; i < roomsSize; i++) if(visited[i] == 0) return false;
    return true;
}