[프로그래머스] 네트워크

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

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

 

DFS 알고리즘을 통하여 0 ~ n-1 을 분할한다. 컴퓨터의 번호가 check 안 되어 있을 때(check[i] == 0), 재귀함수를 통해 이어져 있는 컴퓨터들의 번호를 다 check 해주고(check[i] = 1) answer 에 1을 더해준다.

 

def solution(n, computers):
    answer = 0
    check = [0] * n
      
    for i in range(n):
        if check[i] == 0:
            rf(i, computers, check)
            answer += 1
    
    return answer

def rf(i, computers, check):
    if check[i] == 0:
        check[i] = 1
        
        for j in range(len(computers)):
            if i != j and computers[i][j] == 1:
                rf(j, computers, check)
            
print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]])) # 2