[Basic_Algorithm] [BFS/DFS]

   트리는 크게 두 가지 방식으로 탐색(traverse)될 수 있다. 하나는 깊이 우선 탐색인 Depth-Frist-Search이고, 또 다른 것은 Breadth-Frist-Search이다. 프로그래머스의 연습문제를 통해서 DFS를 실제 문제에서 어떻게 적용해서 푸는지 알아보는 시간을 갖도록 해보자. 

먼저 문제는 다음과 같았다. (출처; https://programmers.co.kr/ 프로그래머스 > 코딩테스트 연습 > 깊이/너비 우선탐색 > 네트워크)

""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""

처음에 어떻게 접근했냐면, 1) 각 컴퓨터 해당하는 노드를 키로 만들고, 그것들과 연결된 또 다른 컴퓨터에 대한 정보를 value값으로 만들어서(딕셔너리, set활용), Computer[i]를 받을 때마다 0이 아닌 index(컴퓨터 값)을 받아서 해당 value값을 업데이트 하는 식으로 진행했다. 2) 물론, 두 컴퓨터가 연결되어 있다면 두 컴퓨터에 해당하는 value값들을 서로 동기화하도록 해주었다.3)마지막으로는 각 value값들 중에서 유일한 값들이 몇 개인지 세는 작업을 하였다. 

import numpy as np

def solution(n, computers):
    network = {} #각 network에 해당하는 딕셔너리 생성
    
    for i in range(n):
        network[i] = set() 
        #Computer의 리스트를 받아서, 0이 아닌 index(컴퓨터 넘버)값들을 set에 추가하는 방식     
        network[i].update(np.nonzero(computers[i])[0]) 
        
    for i in range(n): 다만, i와 j가 연결되어 있다면, i와 j의 set들을 모두 일치하도록 update해주는 방식
        for j in network[i]:
            if j != i:
                network[j].update(network[i])
            
    
    answer1 = 1
    answer = [network[i]] #마지막으로, unique한 set이 몇 개인지 세도록 하였다. 
    for i in network.values(): #set들로 구성된 list의 경우 set(list)를 할 수 없었다.
        if i not in answer:
            answer.append(i)
            answer1 +=1
        
    
    return answer1

-> 하지만, 이 방법으로는 BFS/DFS를 활용했다고 볼 수 없어서 다시 푼 코드는 아래에 있다. 위의 방식보다 훨씬 시간이 적게 들었다(거의 절반 정도 효율적으로 시간을 사용하였다.)

아래의 방식은, 컴퓨터 노드들을 DFS로 방문하면서 하나의 네트워크 하에서는 서로 연결되어 있으므로 모두 방문이 가능하기 때문에 네트워크가 끊길 때마다 answer을 +1더해주면서 구하는 방식이다. 이를 위해서 DFS와 관련한 함수를 Solution함수 하위로 만들었으며, visited = [], 0과 1로 구성된 노드를 방문했는지에 대한 정보를 담은 리스트 변수가 사용되었다. 

* 보통, 두 노드가 연결되어 있는지 알아보는 멤버십 테스트의 경우 셋의 자료형보다 리스트의 자료형이 보다 노드들을 순회하는데 효율적이라고 한다. 셋을 리스트로 바꿀 경우 멤버십 테스트의 시간 복잡도는 O(n)이라고 한다.