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

🌭 문제 설명

• 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

---

🍗 제한 사항

---

🎁 입출력 예시

• 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

• 첫째 줄에 연결 요소의 개수를 출력한다.

---

😎 나의 풀이

import sys
from collections import deque

input = sys.stdin.readline

N,M = list(map(int, input().split()))

# 인접리스트 (각 노드가 어떤 노드랑 연결됐는지 저장)
adj = [[] for _ in range(N)]

for _ in range(M): # M개의 간선 입력받음
  u, v = list(map(int, input().split()))
  
  # 인접 노드 추가
  # 0번부터 시작하는 리스트를 사용하기 위해 -1 해줌
  adj[u - 1].append(v - 1)
  adj[v - 1].append(u - 1)

# visit 배열
visit = [False] * N
# 연결 요소의 개수
count = 0

for i in range(N): # 0부터 N-1까지 확인
  if visit[i]: # visit 배열에 체크가 되어있으면 넘어간다. (이미 방문한 노드 건너뜀)
    continue
  
  # bfs를 시작
  # 시작점(새로운 연결 요소)을 찾았기 때문에 count + 1
  count += 1
  
  # BFS를 위한 큐 선언
  queue = deque([i])
  # visit 배열에 방문 체크
  visit[i] = True
  
  # 큐가 빌때까지 반복
  while len(queue) != 0:
    # 큐에서 노드를 하나 꺼내온다.
    u = queue.popleft()
    
    # 현재 노드와 연결된 노드를 탐색.
    for v in adj[u]:
      # 방문안한 노드들만 확인하고 싶기 때문에
      # visit 배열에 체크가 안되어있는 노드들을 큐에 넣어준다.
      if not visit[v]: # 방문하지 않았다면
        # 큐에 넣는다.
        queue.append(v)
        # 방문 체크
        visit[v] = True
        
print(count)

1. BFS를 이용한 풀이

---

🧵 다른 풀이

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# dfs 함수
def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

n, m = map(int, input().split()) # 정점의 개수, 간선의 개수
graph = [[] for _ in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

count = 0 # 연결 노드의 수
visited = [False] * (n+1)
for i in range(1, n+1):
    if not visited[i]:
        dfs(graph, i, visited)
        count += 1 # dfs 한 번 끝날 때마다 count+1

print(count)

1. DFS를 이용한 풀이이다.

---

• BFS의 개념을 공부하고 풀어봤는데 BFS를 활용할 수 있는 기본적인 문제 인 것 같다.