[Graphs - DFS][Medium] 841. Keys and Rooms

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

LeetCode - The World's Leading Online Programming Learning Platform

Q. 각 배열안의 숫자는 각 접근 가능한 index를 의미한다.

  0 번 index는 접근 가능하다고 할때, 모든 index를 접근 가능한지 여부를 반환하라.

 

 

 

Solution

 tree의 접근법과 거의 같다고 생각하면 맞다고 본다.

 다만 그래프는 가지가 여러개 일수 있고, 방향에 상하가 없다. 따라서 cycle이 생길 수 있다. 

 어느 방식이든, 이 노드들을 모두 visit했는지 확인하는데, cycle이 생기면 이미 visit 했으므로 멈춰야 한다.

 이를 생각하며 로직을 코드로 만든다. 

 

 

 BFS든 DFS든 방법은 상관 없을 것 같다. 

 BFS로 코드를 만들어 본다. 

bool canVisitAllRooms(vector<vector<int>>& rooms)
{
    if (rooms.size() <= 0)	return false;

    vector<bool> vVisit;
    vVisit.resize(rooms.size(), false);
    vVisit[0] = true;

    queue<int> qBuff;
    for (int k = 0; k < rooms[0].size(); ++k)
        qBuff.push(rooms[0][k]);

    while (!qBuff.empty())
    {
        int idx = qBuff.front();
        qBuff.pop();
        if (vVisit[idx])
            continue;

        vVisit[idx] = true;
        for (int k = 0; k < rooms[idx].size(); ++k)
            qBuff.push(rooms[idx][k]);
    }

    for (int k = 0; k < vVisit.size(); ++k)
    {
        if (!vVisit[k])	return false;
    }
    return true;
}

 

다행히 방향은 맞는 듯 하다.

 

 

이번에는 DFS로 시도 해 본다. 

void canVisit(vector<bool>& vVisit, int idx, vector<vector<int>>& rooms)
{
    if (vVisit[idx])	return;

    vVisit[idx] = true;
    for (int q = 0; q < rooms[idx].size(); ++q)
    {
        int curIdx = rooms[idx][q];
        canVisit(vVisit, curIdx, rooms);
    }
}
bool canVisitAllRooms(vector<vector<int>>& rooms) 
{
    if (rooms.size() <= 0)	return false;

    vector<bool> vVisit;
    vVisit.resize(rooms.size(), false);

    canVisit(vVisit, 0, rooms);

    for (int k = 0; k < vVisit.size(); ++k)
    {
        if (!vVisit[k])	return false;
    }
    return true;
}

 

 

결과는 대동소이 하다.