프로그래머스 네트워크 코드 및 해설 (파이썬)

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

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

 

DFS를 수행하는 함수 dfs를 정의하고, 모든 컴퓨터를 방문할 때까지 dfs를 반복합니다. 우선 0번째 컴퓨터부터 시작해서 이와 직/간접적으로 연결되어 있는 모든 컴퓨터들 방문합니다. 이후에도 아직 방문하지 않은 컴퓨터가 있으면 answer를 하나씩 증가시키고, 방문하지 않은 컴퓨터 중 번호가 가장 작은 것에서부터 시작해 다시 dfs를 호출합니다. 모든 컴퓨터를 방문하면 반복을 종료하고 answer를 반환합니다.

 

https://codlingual.tistory.com/182

DFS, BFS

 

def dfs(node, computers, visited):
    visited[node] = True 
    
    for i, neighbor in enumerate(computers[node]):
        # 인접노드 중 자기 자신이 아니고 아직 방문하지 않은 노드에 대해 
        if neighbor > 0 and i != node and visited[i] == False:
            dfs(i, computers, visited)
    return visited

def solution(n, computers):
    answer = 1
    visited = [False] * n
    startNode = 0
    
    # 모두 방문할 때까지 
    while True: 
        visited = dfs(startNode, computers, visited)
        if False in visited:
            startNode = visited.index(False)
            answer += 1
        else:
            break

    return answer