[백준] 11724 연결 요소의 개수 (python)

#1 BFS 첫 번째 시도 (실패 - 시간초과)

from collections import deque

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]  # 0번 제외, 1번부터 n번까지
visited = [False]*(n+1)  # 마찬가지로 0번 제외하고 각 노드당 방문확인 배열

count = 0   # 연결 개수

for _ in range(m):   # 간선 개수만큼 노드와 노드 이어붙이기
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)   # 양방향(무방향)

def bfs(start):
    queue = deque([start])  # 시작 노드를 큐에 추가
    visited[start] = True  # 방문한 것으로 처리
    while queue:  # 큐가 비어있지 않을 때
        node = queue.popleft()  # 맨 앞 노드 빼내기
        for i in graph[node]:  # 맨 앞 노드와 연결되어있는 정점들 체크
            if not visited[i]:  # 아직 방문하지 않았다면
                visited[i] = True  # 방문한 것으로 처리
                queue.append(i)  # 큐에 추가함으로써 i 노드 기준 인접한 정점들 탐색이 가능하도록 함

for i in range(1, n+1):   # 인덱스는 1번부터
    if not visited[i]:
        if not graph[i]:  # 연결된 노드가 존재하지 않는 경우
            count += 1
            visited[i] = True
        else:
            bfs(i)  # 연결된 정점이 있으면 방문했다가 오기
            count += 1

print(count)

• 일단 input으로 짜두고 sys.stdin.readline으로 바꾸는데 습관화가 안 되어있는 바람에 까먹고 제출했다가 시간 초과 발생! 잊지말자 sys!

#2 BFS 두번째 시도 (성공)

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]  # 0번 제외, 1번부터 n번까지
visited = [False]*(n+1)  # 마찬가지로 0번 제외하고 각 노드당 방문확인 배열

count = 0   # 연결 개수

for _ in range(m):   # 간선 개수만큼 노드와 노드 이어붙이기
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)   # 양방향(무방향)

def bfs(start):
    queue = deque([start])  # 시작 노드를 큐에 추가
    visited[start] = True  # 방문한 것으로 처리
    while queue:  # 큐가 비어있지 않을 때
        node = queue.popleft()  # 맨 앞 노드 빼내기
        for i in graph[node]:  # 맨 앞 노드와 연결되어있는 정점들 체크
            if not visited[i]:  # 아직 방문하지 않았다면
                visited[i] = True  # 방문한 것으로 처리
                queue.append(i)  # 큐에 추가함으로써 i 노드 기준 인접한 정점들 탐색이 가능하도록 함

for i in range(1, n+1):   # 인덱스는 1번부터
    if not visited[i]:
        if not graph[i]:  # 연결된 노드가 존재하지 않는 경우
            count += 1
            visited[i] = True
        else:
            bfs(i)  # 연결된 정점이 있으면 방문했다가 오기
            count += 1

print(count)

채점 결과

#1 DFS (성공)

import sys
input = sys.stdin.readline

sys.setrecursionlimit(5000)  # 재귀 함수호출의 한도를 높여주기

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]  # 각 노드마다 가지고 있는 연결된 정점들 배열
visited = [False]*(n+1)  # 각 노드마다 방문 했는지 안 했는지

count = 0

# 하나의 노드에 연결되어 있는 정점들을 방문하기 위한 용도
def dfs(start, depth):
    visited[start] = True
    for i in graph[start]:
        if not visited[i]:
            dfs(i, depth + 1)

# 입력받은 숫자로 무방향(양방향) 그래프 구성
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 연결되어있는 요소 개수 세기 위한 부분
for i in range(1, n+1):
    if not visited[i]:
        if not graph[i]:
            count += 1   # 고립되어있기 때문에 바로 +1
            visited[i] = True
        else:
            dfs(i, 0) 
            count += 1   # 연결되어있는 정점들 모두 방문한 후 +1

print(count)

채점 결과

BFS와 DFS 두 가지 풀이 결과, 속도나 메모리 면에서 그다지 큰 차이가 없었다!