[DFS/BFS] 네트워크

문제 설명

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

프로그래머스

문제 풀이

• 연결된 노드들을 확인한 후 0번 노드부터 BFS 방식으로 탐색하면서 한번에 연결지을 수 있는 것들 모두 연결
• 0번 노드로부터의 탐색이 끝나면 1,2,3,4,5,...n-1번 노드 순서대로 탐색하는데 이미 탐색했던 거라면 continue
• 탐색하지 않았더라면 새로운 네트워크의 발견이므로 answer+1

소스 코드

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [False]*n
    gr = [[] for i in range(n)]
    for i in range(n):
        for j in range(i+1,n):
            if computers[i][j]==1:
                gr[i].append(j)
                gr[j].append(i)
    for i in range(n):	#순서대로 탐색
        if visited[i]==True:
            continue
        answer+=1
        visited[i]=True
        q = deque()
        q.append(i)
        while(q):	#BFS
            cur = q.popleft()
            for next in gr[cur]:
                if visited[next]==True:
                    continue
                visited[next]=True
                q.append(next)

    return answer
    

if __name__=='__main__':
    n = int(input().rstrip())
    com = []
    while(True):
        op = list(map(int,input().rsplit()))
        if not op:
            break
        com.append(op)
    print(solution(n,com))