Если стены представлять как рёбра, а комнаты – как вершины, то можно начать с минимального остовного дерева, чтобы снизить затраты, потом добавить вес, учитывающий защищённость, и прогнать алгоритм максимального потока или разбиения графа – вполне достаточно для быстрого прототипа.