BOJ - 11724

백준 문제 링크
연결 요소의 개수

❓접근법

1. BFS를 사용했다.
2. 아래 그림을 봤을 때,
   예제 1은 연결 요소가 2개인 그래프이고,
   예제 2는 연결요소가 1개인 그래프이다.
3. 예제 1은 2번의 BFS로 모두 방문할 수 있고,
   예제 2는 1번의 BFS로 모두 방문할 수 있는 것이다.
4. for 문으로 lst를 살펴볼 때, not visited[i] 이면
   bfs(i)를 실행, answer + 1
5. answer를 출력하면 끝!

👌🏻코드

from collections import deque
import sys


N,M = map(int, sys.stdin.readline().split())
lst = [[] for _ in range(N+1)]
visited = [False] * (N+1)

answer = 0

for _ in range(M):
    x,y = map(int, sys.stdin.readline().split())
    lst[x].append(y)
    lst[y].append(x)
    
def bfs(v):
    queue = deque()
    queue.append(v)
    
    visited[v] = True
    
    while queue:
        v = queue.popleft()
        
        for i in lst[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
                
for i in range(1, N+1):
    if not visited[i]:
        bfs(i)
        answer += 1

print(answer)

import sys 없이 제출하니, 시간 초과가 나서 그 점 유의하면 좋을 것 같다.