プログラマネットワーク

15148 ワード
テキストリンク
最初の試みでは、問題を完全に誤って理解した.
😇 初めての試み
from collections import deque

def bfs(dq, n, computers):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while dq:
        y, x = dq.popleft()
        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if computers[ny][nx] == 1:
                dq.append((ny, nx))
                computers[ny][nx] = 0
                
def solution(n, computers):
    answer = 0
    for j in range(n):
        for i in range(n):
            if computers[j][i] == 1:
                answer += 1
                dq = deque([(j, i)])
                bfs(dq, n, computers)

    return answer
上の解答はもちろん失敗したので、コンピュータの位置ではなく、接続関係を表すグラフです.
では、接続関係を表すグラフィックが現れた場合、bfsはどのように使用すればいいのでしょうか.
接続されたオブジェクトをarrayに配置し、各オブジェクトコンピュータに接続されたオブジェクトconnectをT/Fとして表すと、接続があるかどうかを知ることができます.
グラフよりは見慣れないが、より簡単な論理で解決できる.
より具体的には、0番目のコンピュータに接続されたコンピュータをTに変換し、接続されたコンピュータのインデックスをキューに入れ、接続されたコンピュータについても同様の方法で接続されたコンピュータを検索し、Tに変換することで、ネットワークに接続されたグループを見つけることができる.
🤗 二次試行
BFSプール
from collections import deque

def BFS(dq, n, computers, visited):
    while dq:
        current = dq.popleft()
        for connect in range(n):
            if visited[connect] == False and computers[current][connect] == 1:
                visited[connect] = True
                dq.append(connect)

                
def solution(n, computers):
    answer = 0
    visited = [False for _ in range(n)]
    dq = deque([0])
    
    for idx in range(n):
        if not visited[idx]:
            dq.append(idx)
            BFS(dq, n, computers, visited)
            answer += 1
            
    return answer
新しい方法もあります.過去の私はユニオンフィールドで解決しました...ほほほ
Union Findプール
def find_parent(parents, x):
    if parents[x] != x:
        parents[x] = find_parent(parents, parents[x])
    return parents[x]

def union_parent(parents, a, b):
    a = find_parent(parents, a)
    b = find_parent(parents, b)
    if a > b:
        parents[a] = b
    else:
        parents[b] = a

def solution(n, computers):
    parents = [0 for _ in range(n)]

    for i in range(n):
        parents[i] = i

    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                union_parent(parents, i, j)

    for i in range(n):
        find_parent(parents, i)

    count = 0
    tmp = -1
    for p in parents:
        if p != tmp:
            tmp = p
            count += 1
    return count
01.OSI 7層
Redisでのサブスクリプションとパブリケーション