[テストエンコーディング]ネットワーク


問題の説明
ネットワークとは、コンピュータ間で情報を交換する接続形式を指す.例えば、コンピュータAがコンピュータBに直接接続され、コンピュータBがコンピュータCに直接接続されている場合、コンピュータAとコンピュータCは間接的に接続されて情報を交換することもできる.そのため、コンピュータA、B、Cは同じネットワーク上に存在する.
指定されたコンピュータの個数nが、接続情報を含む2次元配列コンピュータをパラメータとする場合、ネットワークの個数を返すために解関数を記述します.
せいげんじょうけん
コンピュータの個数nは、1又は複数の200以下の自然数である.
各コンピュータは0からn−1までの整数で表される.
i番コンピュータがj番コンピュータに接続されている場合、コンピュータ[i][j]は1として表される.
コンピュータ[i][i]は常に1.
I/O例
n computers return
3 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 2
3 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] 1
I/O例説明
例1
次の2つのネットワークがあります.
例2
次のようにネットワークがあります.
再帰関数を用いてkに関連するすべての数字をcompリストに入れる.このプロセスが繰り返される回数はネットワークの個数である.
Pythonの場合、再呼び出し回数は1000回に制限されているため、以下のコードのようにモジュールをインポートする必要があります.
私が書いたコード
## 재귀 횟수를 늘려주기 위함 : 10**7번까지
import sys
sys.setrecursionlimit(10**7)

def go(a, comp, answer, computers, n):
    for i in range(n):
        if a != i and i not in comp and computers[a][i] == 1:
            comp.add(i)
            go(i, comp, answer, computers, n)
    answer += 1
    comp.add(a)
    return answer

def solution(n, computers):
    answer = 0
    comp = set()
    k = 0
    
    while len(comp) < n:
        if k not in comp:
            answer = go(k, comp, answer, computers, n)
            # print(comp)
        k += 1
    
    return answer