ネットワーク

9572 ワード
プログラマ テキストリンク

🔗 質問リンク


https://programmers.co.kr/learn/courses/30/lessons/43162

問題の説明



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

    • 💡 プール(言語:Python)


    DFS,BFSに関する問題であることが分かっていても,コードを記述することは容易ではない.学んで役に立つのはやはり難しい.人の解答を見てから、練習して書きます.今度似たような問題があったら、その時になったらよく練習しましょう.

    ①DFSプール

    이 문제는 DFS가 속도가 더 빨리 나왔다.
    ## DFS : 끝까지 깊게 들어가는 탐색
def dfs(n, cur, computers, visited):
    # 방문 여부 리스트에 방문 처리
    if visited[cur] == False:
        visited[cur] = True

    for con in range(n):
        if cur != con and computers[cur][con] == 1:
            # 재귀함수로 미 방문 요소 존재시 방문
            if visited[con] == False:
                dfs(n, con, computers, visited)

def solution(n, computers):
    answer = 0
    # 방문 여부 리스트
    visited = [False for i in range(n)]
    # cur = 현재 컴퓨터
    for cur in range(n):
        if visited[cur] == False:
            # dfs 한 사이클 = 1개의 네트워크
            dfs(n, cur, computers, visited)
            answer += 1
            
    return answer

    ②解析BFS

    ## BFS : 같은 레벨 우선 탐색
from collections import deque

def bfs(n, cur, computers, visited):
    # 맨 처음 시작 컴퓨터 방문 처리
    visited[cur] = True
    # 큐에 시작점 넣어주기
    queue = deque([cur])

    # 큐의 원소가 모두 사라질 때까지 반복
    while queue:
        # 큐 안에서 루프 돌릴 때 방문 처리 
        cur = queue.popleft()
        visited[cur] = True
        
        for con in range(n):
            if cur != con and computers[cur][con] == 1:
            # 미 방문 요소 존재시 큐에 추가해 방문
                if visited[con] == False:
                    queue.append(con)

def solution(n, computers):
    answer = 0
    # 방문 여부 리스트
    visited = [False for i in range(n)]
    # cur = 현재 컴퓨터
    for cur in range(n):
        if visited[cur] == False:
            # bfs 한 사이클 = 1개의 네트워크
            bfs(n, cur, computers, visited)
            answer += 1
            
    return answer
    210616 Wed
    Props