[python] 네트워크 문제풀이(DFS정복!)

처음엔 약간의 편법으로 접근하려 했다.

[1, 1, 0], [1, 1, 0], [0, 0, 1]

이렇게 자신의 인덱스 넘버는 무조건 1이고,

그 외에 1이 있다면 연결되어있다는 뜻이니,

 

이중 포문으로 탐색하면서,

자신 외에 1의 인덱스 넘버를 저장하고,

set으로 중복제거 후 갯수를 세는 방식으로 해봤다.

 

즉 DFS, BFS도 안쓰고 그냥 편법을 쓴것이다.

 

def solution(n, computers):    
     alist = []
     for idx, val in enumerate(computers):
         for idxx, vall in enumerate(val):
             if idxx != idx and vall == 1:
                     alist.append(idx)

     alist = set(alist)
     return n-len(alist)+1

이렇게 실행하니, 기본제공 2개의 테스트케이스는 통과하나,

통과를 위한 13개의 테스트케이스 중 4, 5, 7번이 에러가 났다.

아무리 본 코드를 봤을때

발전 가능성이 없을 것 같아서 정공법으로 DFS를 꺼내들었다.

 

시간복잡도가 굉장하나... (2중 while문 + "n not in visited"도 visited 배열의 크기만큼 탐색하니... 어휴)

통과는 할 수 있었다.

 

def solution(n, computers):
    stack = [0]
    visited = []
    toVisit = [i for i in range(n)]
    print(toVisit)
    answer = 0
    while toVisit:
        while stack:
            n = stack.pop()
            if n not in visited:
                visited.append(n)
                tlist = [i for i, 
                         val in enumerate(computers[n]) 
                         if val==1 and i not in visited]
                stack = stack+tlist
        answer += 1
        toVisit = list(set(toVisit)-set(visited))
        if toVisit:
            stack = [toVisit[0]]
        
    
    return answer

 

다시한번 본질적으로 DFS를 공부할 수 있었고,

[i for i, val in ... ] 과 같이 파이썬 특유의 코드 모양도 여러번 활용해볼 수 있어서

꽤나 보람찼다.

 

이번 공부를 통해 얻은 결론을 다시 한번 정리했다.

gogoonbuntu.tistory.com/23?category=893844