99클럽 코테 스터디 6일차 TIL 프로그래머스 네트워크

프로그래머스 네트워크

이 문제는 네트워크 개수를 구하는 문제로 주어진 연결관계를 따라 연결 여부를 확인하고, 연결된 네트워크내의 컴퓨터들을 모두 방문처리하고, 아직 방문처리 되지 않은 컴퓨터에서 다시 시작해서 연결된 네트워크들을 반복 탐색한 수만큼 세주면 된다. 

나는 연결된 네트워크를 탐색하는 알고리즘으로 bfs를 활용했다.

나의 코드

from collections import deque
def solution(n, computers):
    visited=[False for _ in range(n)]
    answer = 0
    for i in range(n):
        if not visited[i]:
            visited[i]=True
            answer+=1
            que=deque()
            que.append(i)
            while que:
                next=que.popleft()
                for j in range(i+1,len(computers[next])):
                    if computers[next][j]==1 and not visited[j]:
                        visited[j]=True
                        que.append(j)
    return answer

회고

이미 이전에 한번 풀었을때 코드를 보면 que 부분을 배열로 놓고, bfs를 pop(0)를 썼었다.

그런데 이 pop(0)는 아마 log(1)이 아닌 log(N)의 시간 복잡도를 가졌던 것으로 문제를 풀면서 한 번 경험해 본 적이 있어, 배열을 deque로 바꾸어 주어 큐의 형태로 log(1)의 시간복잡도를 갖도록 조금 수정해주었다.

이번 테스트케이스에서는 queue가 크게 쌓이지 않아 성능 차이가 거의 없어보였지만, queue가 쌓이는 순간 기하급수적으로 시간차이가 날 것 같다.