[Baekjoon11724] 연결 요소의 개수

문제 11724

DFS

import sys
from sys import stdin
sys.setrecursionlimit(10**7)

def dfs(v):
	# 방문처리
    visited[v] = True
    # graph[v]와 연결된 노드 중 방문하지 않으면 재귀함수를 통해 방문
    for w in graph[v]:
        if not visited[w]:
            dfs(w)

answer=0
N,M = map(int, stdin.readline().split())
graph = [[] for _ in range(N+1)] # 연결된 노드
visited = [False ] * (N+1) # 방문여부

# 연결된 노드 각각에 저장
for _ in range(M):
    u,v = map(int, stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

# 노드 방문이 끝나면 연결요소 추가 answer++
for i in range(1, N+1):
    if not visited[i]:
        dfs(i)
        answer+=1

print(answer)

BFS

from sys import stdin
from collections import deque

N, M = map(int, stdin.readline().split())

def bfs(v):
	# 방문처리
    visited[v] = True
    # 큐 선언 및 첫 번 째 노드 시작 저장
    queue = deque([v])
    
    # 큐가 빌 때까지 노드를 방문, 해당 노드와 연결된 노드 중 방문하지 않은 노드가 있다면 방문
    # 그리고 큐에 삽입
    while queue:
        w = queue.popleft()
        for i in graph[w]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
            
    
answer=0
graph = [[] for _ in range(N+1)]
visited=[False for _ in range(N+1)]

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

for i in range(1,N+1):
    if not visited[i]:
        bfs(i)
        answer+=1
    
print(answer)

위: BFS
아래 2개: DFS
시간초과는 sys.stdin.readline() 사용 안 해서