Графы. Поиск ключей от комнат. Python

Question

Помогите решить задачу. Скорее всего неверный алгоритм. Я решаю ее на stepik и там не показывает какой тест не проходит, отчего не пойму где ошибка. И решение не засчитывает. Я попробовал решить без переменной v, т.к. не понятно как ее использовать.

Задача:

Представьте, что вы попали в большой замок, в котором N комнат (под номерами 0..N-1), а вы находитесь в комнате под номером 0. В каждой комнате спрятаны ключи, которые позволяют попасть в другую комнату.

В каждой комнате i есть список чисел rooms[i], обозначающий список ключей, который хранится в этой комнате. Каждый ключ j открывает некоторую комнату под номером v: rooms[i][j] = v

В начале все комнаты закрыты. Верните True, если все комнаты в замке могут быть открыты, а иначе верните False.

Вот мой код:

class Solution:        
def canVisitAllRooms(self, rooms: list):
    verifyList=[]
    tst = [i for i in range(len(rooms))]
    for i in range(len(rooms)):
        tf=0
        if len(rooms[i])>0:
            for j in rooms[i]:
                if i != j and j in range(len(rooms)): tf += 1
                print('ключ из комнаты', i, 'открывает комнату', j)
            print('совпадений - ', tf)
            verifyList.append(tf)

    if 0 in verifyList: return False
    else: return True

Answer 1

Решил в итоге задачу, за неимением ответов на вопрос) получилось вот так:

def canVisitAllRooms(self, rooms: list):
    # создаем закрытые комнаты
    visited = [False] * (len(rooms))

    def dfs(s, visited):
        #если комната открыта, то true
        if visited[s]:
            return True
        # иначе открываем текущую комнату
        visited[s] = True
        # и проверяем ключи из этой комнаты
        for neighbor in rooms[s]:
            #print(neighbor)
            dfs(neighbor, visited)


    s=0
    #print(dfs(0, visited))
    dfs(0, visited)

    # проверка открытых комнат
    if False in visited: return False
    else: return True

Answer 2

Предлагаю итеративное решение.

Оно имеет следующие преимущества:

Максимальная, дефолтная глубина рекурсии в Python 1000 вызовов, соответственно рекурсивное решение не сможет обработать больше 1000 комнат.
Для хранения посещённых комнат используется структура данных set, что позволяет проверять посещена ли комната за константное время - O(1).

Алгоритм:

Создаём набор (set) ключей, помещаем в него ключ от комнаты № 0.
Достаём ключ из набора, если он от непосещённой комнаты, заходим в неё.
Добавляем все ключи из новой комнаты в набор ключей.
Добавляем комнату в посещённые.
Если в наборе остались ключи, возращаемся в пункт 2.
Возращаем результат сравнения количества посещённых комнат с общим количеством.

class Solution:
    def canVisitAllRooms(self, rooms):
        key_set = {0} 
        visited = set()

        while key_set:
            key = key_set.pop()

            if key not in visited:
                key_set.update(rooms[key])
                visited.add(key)

        return len(visited) == len(rooms)

БЛОГ НА HUSL

Графы. Поиск ключей от комнат. Python

Ответы (2 шт):