[Programmers/Python/奥行き、幅優先ナビゲーション(DFS,BFS)]-ネットワーク

3262 ワード
コーディングテスト テキストリンク
ソース
https://programmers.co.kr/learn/courses/30/lessons/43162?language=python3

Q.


問題の説明
ネットワークとは、コンピュータ間で情報を交換する接続形式を指す.例えば、コンピュータ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例

    私の答え


    1


    dictでグラフを作成します.
    def bfs(graph, start_node):
    visit = list()
    queue = list()

    queue.append(start_node)

    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])

    return visit

def solution(n, computers):
    answer = 0
    networks = {computer : [] for computer in range(n)}

    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if computers[i][j] == 1:
                  networks[i].append(j)


    visit = bfs(networks, 0)

    return n-len(visit)+1


    問題は、4台のパソコンで0-1、2-3が接続され、2つのネットワークがあれば、このような状況になるということです.つまり切れたパソコンにアクセスできないので、この問題を解決してみます.

    2

    def solution(n, computers):
    answer = 0
    networks = {computer : [] for computer in range(n)}

    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if computers[i][j] == 1:
                  networks[i].append(j)
    
    visit = list()
    queue = list()

    start = 0

    while(networks):
        tmp = list()
        queue.append(start)
        while queue:
            node = queue.pop(0)
            if node not in tmp:
                tmp.append(node)
                queue.extend(networks.pop(node))
                start += 1
        visit.append(tmp)

    return len(visit)


    https://programmers.co.kr/questions/13874
    接続が双方向でない場合も考慮...他の解答は考えられないので、他の人の解答を参考にして、以下のように書きました.

    3(通過)

    def solution(n, computers):
    answer = 0
    bfs = []
    visited = [0]*n

    while 0 in visited:
        x = visited.index(0)
        bfs.append(x)
        visited[x] = 1
        
        while bfs:
            node = bfs.pop(0)
            visited[node] = 1
            for i in range(n):
                if visited[i] == 0 and computers[node][i] == 1:
                    bfs.append(i)
                    visited[i] = 1
        answer += 1
    return answer
    [React] Hooks: useState
    rsyncとsshによるインスタンスのバックアップ