[프로그래머스] 파이썬 _ 네트워크 ⭕️

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

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

 

문제유형 : DFS/BFS

문제풀이 :

• 전형적인 DFS(BFS)문제로 "연결된 덩어리들이 몇개냐" 구하는 문제
• DFS를 통해 노드들을 방문하는데, 자기자신이 아니면서 연결된 노드가 있을때, 해당노드가 아직 방문 전이면 재귀적으로 해당노드를 출발점으로 하여 DFS를 호출한다.
• 더이상 연결된 노드들이 없을때 DFS의 재귀가 끝나므로 그때 answer에 1을 추가해준다.
• 아직 방문전인 노드가 있다면 다시 그 노드를 출발점으로 하여 DFS를 호출할 수 있도록 한다.
• 백준에서 푼 문제랑 거의 똑같아서 금방 풀 수 있었다. 

정답코드:

global visited
def solution(n, computers):
    answer = 0
    global visited
    visited = [False for _ in range(n)]

    for i in range(n):
        if visited[i] == False:
            dfs(i, n, computers)
            answer += 1

    return answer

def dfs(start,n, computers):
    global visited
    visited[start] = True

    for i in range(n):
        #자기자신이 아니면 
        if i!=start:
            # 해당 노드와 연결되있으면서 아직 방문전이면 
            if computers[start][i] == 1 and visited[i] == False:
                dfs(i, n, computers)