문제 출처 : https://www.acmicpc.net/problem/11724
난이도 : 실버 2

문제 파악

무방향 그래프가 주어진다.
여기서 연결 요소(Connected Component) 의 개수를 구해야 한다.

• 연결 요소 = 서로 도달 가능한 노드들의 “덩어리”
• 그래프가 여러 덩어리로 나뉘어 있을 수 있음
• 결국 “아직 방문하지 않은 노드에서 BFS/DFS를 시작한 횟수”가 답이 된다.

해결 아이디어

1. 그래프를 인접 리스트로 만든다.
2. visited 배열로 방문 여부를 관리한다.
3. 1 ~ N을 순회하면서:
   • 아직 방문하지 않은 노드를 만나면 BFS를 돌려서 그 덩어리를 전부 방문 처리한다.
   • BFS를 한 번 시작했으니 연결 요소 개수(cnt)를 1 증가시킨다.

시간초과난 코드

import sys
input = sys.stdin.readline
from collections import deque

# 연결 요소의 개수 구하기
N, M = map(int,input().split())

# 완전탐색으로 BFS 돌며 cnt를 올리면 될 것 같다.

cnt = 0

graph = [
    [] for _ in range(N+1)
]

visited = [False] * (N+1)
for _ in range(M):
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)


def BFS(start):
    global cnt 

    queue = deque()
    queue.append(start)

    while queue:
        node_index = queue.popleft()
        visited[node_index] = True 

        for next_node_index in graph[node_index]:
            if not visited[next_node_index]:
                queue.append(next_node_index)
        
    cnt += 1 # BFS 한번 다 돌면 cnt값 +1


for i in range(1,N+1):
    if not visited[i]:
        BFS(i)

print(cnt)

visited 배열에 방문처리 타이밍 을 popleft() 할 때 True로 해주었더니 시간초과가 났다.

• 방문처리를 popleft() 시점에 하면
  “같은 노드가 여러 번 큐에 들어가는 중복 삽입”이 발생할 수 있다.
• 안전하고 빠른 방식은
  큐에 넣는 순간(append) visited를 True로 바꾸는 것이다.
  → 그래야 같은 노드가 다시 큐에 들어가는 걸 원천 차단한다.

수정된 정답 코드

import sys
input = sys.stdin.readline
from collections import deque

# 연결 요소의 개수 구하기
N, M = map(int,input().split())

# 완전탐색으로 BFS 돌며 cnt를 올리면 될 것 같다.

cnt = 0

graph = [
    [] for _ in range(N+1)
]

visited = [False] * (N+1)

for _ in range(M):
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)


def BFS(start):
    global cnt 

    queue = deque()
    queue.append(start)
    visited[start] = True
    
    while queue:
        node_index = queue.popleft()
        # visited[node_index] = True  처음에 여기다가 방문 로직을 넣었는데, 그러면 중복 삽입이 가능해져서 시간초과가 난다. append할때 방문처리하자.

        for next_node_index in graph[node_index]:
            if not visited[next_node_index]:
                queue.append(next_node_index)
                visited[next_node_index] = True
        
    cnt += 1 # BFS 한번 다 돌면 cnt값 +1


for i in range(1,N+1):
    if not visited[i]:
        BFS(i)

print(cnt)