7/28 Coding Test

✅ BOJ

🎈 11724 연결 요소의 개수

무방향 그래프가 주어지고 그래프 내 연결 요소의 개수를 구하는 프로그램

• 입력값 : 첫 줄 (정점개수, 간선개수), 둘째 줄 (간선 양 끝점)
• 출력값 : 연결 요소 개수

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (n+1)

def bfs(start, graph, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

cnt = 0
for i in range(1, n+1):
    if not visited[i]:
        bfs(i, graph, visited)
        cnt += 1
print(cnt)

< 풀이 과정 >
전형적인 BFS, DFS 경로탐색 문제
주어진 경로를 탐색하며 연결되어있는 노드를 한 그룹으로 체킹하고, 연결이 더 이상 이루어지지 않으면 +1 처리한다.
방문하지 않은 곳에 한해 BFS 함수를 한번 돌면 연결된 모든 노드를 탐색하고 cnt + 1이 적용되므로, 그룹마다 한 번씩 BFS를 실행하게 된다.

중요한 것은 sys 라이브러리를 통해 input을 빠르게 받아 대량의 입력에 대해 효과적으로 대응할 수 있고, 재귀 깊이를 제한함으로써 무한 재귀로 인한 크래쉬 문제를 미리 방지하는 것