2022.03.01 [프로그래머스] (python 파이썬) 네트워크

 

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

코딩테스트 연습 - 네트워크

 

---

풀이

이문제는 연결된 노드만 모두 거치면 되는 문제이기 때문에 bfs, dfs모두 사용가능하다.

아래 코드는 bfs를 이용해 해결한 코드이다.

• 우선 입력받은 computers배열에서 각 컴퓨터와 연결된 컴퓨터들을 graph에 담는 작업을 했다.
• computers의 배열은 0번째 컴퓨터부터 순서대로 있으므로 w를 이용해 컴퓨터의 번호를 메겼다.
• 그리고 i[j]==1이면 j번째 컴퓨터가 w와 연결되어있기 때문에 그래프에 추가해주었다.
• 또한 vis를 이용해 해당 컴퓨터에 방문했는지를 확인했다.
•  

from collections import deque
 
def solution(n, computers):
    answer = 0
    graph=[[] for _ in range(n+1)]
    w=0
    for i in computers:
        for j in range(len(i)):
            if i[j]==1 and w!=j:
                graph[w].append(j)
        w+=1
    vis=[False]*(n+1)
    
    def bfs(graph,answer,vis,i):
        deq=deque()
        deq.append(i)
        while deq: 
            i=deq.popleft()
            for a in graph[i]:
                if not vis[a]:
                    deq.append(a)
                    vis[a]=True
 
    for i in range(n):
        if not vis[i]:
            bfs(graph,answer,vis,i)
            answer+=1
    return answer