[코딩테스트] 프로그래머스 - 네트워크

1. 아이디어 

▪ 방문여부 리스트 초기화

▪ for 문 돌면서 해당 컴퓨터에 방문하지 않았으면

   - 네트워크 개수 += 1 

   - 방문여부 갱신

   - 큐에 해당 컴퓨터 인덱스 넣어주기 

   - bfs

▪ bfs 

   - 큐에서 값하나 꺼내오기

   - 반복문 돌면서 해당 컴퓨터와 연결되어 있고, 아직 방문하지 않은 컴퓨터 찾기

      - 방문 여부 갱신

      - 큐에 해당 컴퓨터 인덱스 추가하기 

2. 시간복잡도

▪ O(n^2)

3. 변수

▪ 인접행렬: int[][]

▪ 방문여부: bool[]

▪ 네트워크의 개수: int

Code

def solution(n, computers):
    chk = [False] * n
    answer = 0
    q = []
    
    for i in range(n):
        if chk[i] == False:
            answer += 1
            chk[i] = True
            q.append(i)

            while q:
                j = q.pop(0)

                for i in range(n):
                    if computers[j][i] == 1 and chk[i] == False:
                        chk[i] = True
                        q.append(i)
               
    return answer

 

프로그래머스