レベル3ネットワーク


質問リンク


質問リンク

<問題を理解>

  • ネットワーク-コンピュータ接続形式
  • n=コンピュータ数(0~200)
  • コンピュータ=各コンピュータと別のコンピュータの接続情報を含む2 Dアレイ
  • 0からn-1、
  • を表す
  • コンピュータ[i][j]:i番コンピュータはj番コンピュータに
  • 接続する.
  • コンピュータ[i][i]=1:常に
  • 固定
  • :ネットワーク数
  • を返します.

    <問題の核心>


  • dfsもbfsも
  • dfs
  • を選びました

  • 各ノード(コンピュータ)にアクセスしているかどうかを確認します.

  • アクセスした場合
  • 標準ノード設定
  • dfs関数を作成し、データムノード上で一連の接続ノードに移動し、
  • 標準ノードで接続されているすべてのノードからなるネットワークが見つかり、cnt+=1
  • すべてのノードがアクセスされるまで、この手順
  • を繰り返します.

  • アクセスなし
    continue

  • dfs関数
  • データムノードである自身はコンピュータ[i][i]=1ロの問題でヒントがあるためアクセス処理を行わなければならない.
  • の隣接ノードに移動し、これらのノードに初めてアクセスした場合は、これらの隣接ノードを再帰的に追跡する必要があります.
  • に移動して終了します.

  • ネットワーク数
    最後に
  • 最終cntを返します
  • <質問クリエイティブ>

  • なし

    <コード>


    1.dfsの使用

    def dfs(n,computers,visited,v) :
        visited[v] = True
        for e in range(n) :
            if computers[v][e] == 1 and visited[e] == False :
                dfs(n,computers,visited,e)
    
    def solution(n, computers):
        visited = [False]*n
        cnt = 0
        while False in visited :
            for v in range(n) :
                if visited[v] == True :
                    continue
                elif visited[v] == False:
                    dfs(n,computers,visited,v)
                    cnt += 1
        return cnt
    
    print(solution(3,[[1, 1, 0], [1, 1, 0], [0, 0, 1]]))
    print(solution(3,[[1, 1, 0], [1, 1, 1], [0, 1, 1]]))

    <実施方法>


    (使用方法、ライブラリなどの原理)

    1.dfsの使用


    1. visited

  • 各ノードが
  • にアクセスしたかどうかを知る.
  • 初期時にはすべてのノードが障害状態初期化
  • にある.
  • while繰り返し文を使用してすべてのノード
  • にナビゲート

    2.dfs関数

  • アクセスされていないノードをデータムノードとして配置し、データムノードの状態をTrueに変更し、隣接ノードが存在するかどうかを確認します.
  • コンピュータ[v][e]=1は[e]=falseにアクセスした.これはコンピュータ[v][e]=1に隣接するノードがあることを意味し、[e]=falseにアクセスしたことを意味し、これは基準ノードである私を排除するためである.
  • は基準ノード上で隣接ノードを探し続け、井戸を1つだけ掘るのでDFS方式と言える.(再帰使用)
  • 3.cntの追加

  • すべてのプロセスが完了すると、cnt+=1のネットワークが作成されます.
  • <結果>


    1.dfsの使用