[프로그래머스💯] 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 네트워크 > 다른 사람의 풀이

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

def solution(n, computers):
    check = [1] * n
    network = 0
    def find(Coms, Com, Com_index):
        check[Com_index] = 0
        for objCom_i,obj_com in enumerate(Com):
            if obj_com:
                if check[objCom_i]:
                    find(Coms, Coms[objCom_i], objCom_i)
    for index, com in enumerate(computers):
        if check[index]:
            find(computers, com,index)
            network += 1
    return network

 

풀이)

 

* check = 컴퓨터가 네트워크에 포함되었는지 여부를 반환합니다. (1: 아직안됨 0: 연결됨)

 

1. 한 컴퓨터에서 연결되는 모든 컴퓨터를 찾아 check 해주는 find 함수를 만듭니다.

2. 본 함수에서는 아직 체킹되지 않은 컴퓨터들의 네트워크를 체크해주는 의미에서 find 함수를 실행합니다.

 

예를들어, (A,C,E) / (B,D) 이렇게 연결되어있는 네트워크라면,

for 문의 첫번째 루프:

A find 함수 한번 실행 => A->C->E            check = [0,1,0,1,0]

두번째 실행 B->D                                   check = [0,0,0,0,0]

(check 에서 1이 아직 네트워크에 포함여부 체크가 안된겁니다.)

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges