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

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

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

 

 

BFS 반복문 풀이

def solution(n, computers):
    #BFS
    visited = [False for _ in range(n)]
    
    count = 0
    stack = []
    
    for index in range(n):
        if not visited[index]:
            count += 1
            stack.append(index)
        
        while stack: # stack이 빌 때까지 돌린다. stack이 비었으면 하나의 네트워크가 끝난 것.
            i = stack.pop()#i번째 열을
            visited[i] = True #방문체크
            
            for j in range(n):#모두 탐색하면서
                if i != j and computers[i][j] == 1:#같지 않고 1인 것이 있으면
                    stack.append(j)#stack에 넣는다.

                    #방문 체크
                    computers[i][j] = -1
                    computers[j][i] = -1
                
    return count

 

DFS 재귀함수 풀이

def DFS(computers, index, visited):
    for j in range(len(computers)):
        if index != j and computers[index][j] == 1:
            computers[index][j] = -1
            computers[j][index] = -1
            visited[j] = True
            DFS(computers, j, visited)

    return

def solution(n, computers):
    visited = [False for _ in range(n)]
    count = 0
    
    for i in range(n):
        if not visited[i]:
            count += 1
            visited[i] = True
            DFS(computers, i, visited)
        
    return count

 

---

 

시간 복잡도

 

최악의 경우 O(N^2)

 

알게 된 점

 

TypeError: 'builtin_function_or_method' object is not subscriptable

stack.append[j]

 

하다보면 가끔 뜨는 에러인데 이김에 정리해두려고 한다.

 

append 함수는 함수이므로 내부의 index나 속성이 없다.

이와 같이 builtin_function_or_method(append 함수)에

subscriptable(내부 index나 속성 참조)를 시도할 경우 나타나는 에러이다.

 

주로 오타로 발생하는 일이 많기 때문에 함수를 사용한 부분에서 괄호를 잘못 사용한 것은 아닌지 체크할 것.

 

 

고찰

 

-

 

Github

프로그래머스 - 네트워크