프로그래머스 - 네트워크

문제

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

프로그래머스

 

 

풀이

연결된 그래프가 총 몇 개인지 구하는 문제다

따라서 모든 노드를 탐색해야 하며, 탐색을 총 몇 번 진행했는지 구하면 된다

 

그래프 탐색을 위해 dfs 알고리즘을 이용한다

 

인접 행렬에서 dfs를 진행하고 노드의 연결 여부에 상관없이 모두 탐색하므로 시간 복잡도는 O(N²)이다

N의 최대값이 200이므로 시간 복잡도는 크게 상관없다

 

코드

python

def dfs(cur, n, computers, visited):
    visited[cur] = True
    
    for next in range(n):
        if computers[cur][next] == 1 and not visited[next]:
            dfs(next, n, computers, visited)
        
 
def solution(n, computers):
    answer = 0
    
    visited = [False] * n
    
    for i in range(n):
        for j in range(n):
            if not visited[i]:
                dfs(i, n, computers, visited)
                answer += 1
    
    return answer