[プログラマ/Python](奥行き/幅優先ナビゲーション(DFS/BFS)ネットワーク

ソース

問題の説明

ネットワークとは、コンピュータ間で情報を交換する接続形式を指す.例えば、コンピュータAがコンピュータBに直接接続され、コンピュータBがコンピュータCに直接接続されている場合、コンピュータAとコンピュータCは間接的に接続されて情報を交換することもできる.そのため、コンピュータA、B、Cは同じネットワーク上に存在する.
指定されたコンピュータの個数nが、接続情報を含む2次元配列コンピュータをパラメータとする場合、ネットワークの個数を返すために解関数を記述します.

せいげんじょうけん

コンピュータの数nは、1つまたは複数の200以下の自然数である.

各コンピュータは、0からn−1までの整数として表される.

コンピュータ番号が

iの場合、コンピュータ[i][j]は1として表される.

コンピュータ[i][i]は常に1である.

I/O例

ncomputersreturn3[[1, 1, 0], [1, 1, 0], [0, 0, 1]]23[[1, 1, 0], [1, 1, 1], [0, 1, 1]]1

I/O例説明

例1
次の2つのネットワークがあります.

例2
次のようにネットワークがあります.

説明する

def solution(n, computers):
    computers = list(set(tuple(coms) for coms in computers))
    for i in range(len(computers)-1):
        for j in range(i+1,len(computers)):
            if any(computers[i][k]*computers[j][k] == 1 for k in range(n)):
                new_com = [computers[i][k] | computers[j][k] for k in range(n)]
                computers.remove(computers[j])
                computers.remove(computers[i])
                computers.append(new_com)
                return solution(n, computers)
    return len(computers)