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

🔑 오늘의 학습 키워드 bfs

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/43162

 

from collections import deque

def solution(n, computers):
    answer = 0
    queue = deque([])
    visited = set()
    
    def bfs(start):
        queue.append(start)
        while queue:
            node = queue.popleft()
            for idx, connect in enumerate(computers[node]):
                if connect == 1 and idx not in visited:
                    queue.append(idx)
                    visited.add(idx)
    
    for i in range (n):
        if i not in visited:
            bfs(i)
            answer += 1
                
    return answer

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

너무 쉬운 bfs문제이다 ..

 

⏰ 예상 시간 복잡도 O( V + E )

제한 사항

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

😎 알고리즘 개요

1. n까지의 컴퓨터를 탐색하면서 연결된 컴퓨터를 찾는다.

    queue = deque([])
    visited = set()
    
    def bfs(start):
        queue.append(start)
        while queue:
            node = queue.popleft()
            for idx, connect in enumerate(computers[node]):
                if connect == 1 and idx not in visited:
                    queue.append(idx)
                    visited.add(idx)

 

2. 탐색되지 않은 컴퓨터를 발견하면 연결된 컴퓨터를 찾는다. (answer + 1)

    for i in range (n):
        if i not in visited:
            bfs(i)
            answer += 1

✅ 오늘의 회고

- 이전에 풀었던 문제라 초기화 하고 다시 풀었다

- 5분 23초 컷

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL