[DFS/BFS/완전탐색] 11724번 - 연결 요소의 개수

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

풀이 시간: 10분 이내

연결 요소의 의미를 몰라서 문제 해결을 할 수가 없어 먼저 연결 요소에 대해 학습하였다.

연결 요소 문제는DFS, BFS로 모두 풀 수 있다.

하지만 직접 코드를 짜본 결과 메모리, 시간 측면에서 둘다 비슷비슷하기 때문에 오류를 고칠 필요가 없는 BFS로 풀기를 추천한다.

 

<연결 요소란?>

• 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
• 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

연결 요소 개수를 구하는 것은 인접한 정접으로 이루어진 그래프 개수를 세는 것과 같다.

 

 

 

[참고] https://velog.io/@polynomeer/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CConnected-Component

연결 요소(Connected Component)

 

---

(풀이1) DFS

1) 문제 해결 아이디어

풀이를 하다 보니 2가지 오류를 만났다.

 

첫번째 오류. 런타임 에러: RecursionError

DFS로 코드를 짜다 보면 자주 만나는 오류로 2줄과 같이 최대 재귀 한도 깊이를 변경해주면 된다.\

 

두번째 오류. 시간 초과

input() 대신 sys.stdin.readline()을 사용하였다.

 

2) 소스코드

import sys
sys.setrecursionlimit(10**6)

# 정점 개수, 간선 개수
n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
res = 0  # 연결 요소 개수

# 그래프 정보
for i in range(m):
  u, v = map(int, sys.stdin.readline().split())
  graph[u].append(v)
  graph[v].append(u)

# DFS
def dfs(v):
  # 삽입, 방문 처리
  visited[v] = True

  # 인접 노드 탐색
  for i in graph[v]:
    # 방문하지 않은 노드라면
    if not visited[i]:
      dfs(i)# 재귀 호출

for i in range(1, n + 1):
 # 해당 정점이 방문하지 않았다면
  if not visited[i]:
    dfs(i)
    res += 1

print(res)

 

(풀이2) BFS

1) 문제 해결 아이디어

별다른 오류없이 바로 성공했기 때문에 BFS로 풀기를 추천한다.

 

2) 소스코드

import sys
from collections import deque

# 정점 개수, 간선 개수
n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
res = 0  # 연결 요소 개수

# 그래프 정보
for i in range(m):
  u, v = map(int, sys.stdin.readline().split())
  graph[u].append(v)
  graph[v].append(u)

# BFS
def bfs(v):
  queue = deque()
  # 시작 노드 삽입, 방문 처리
  queue.append(v)
  visited[v] = True

  while queue:
    v = queue.popleft()
    for i in graph[v]:
      # 방문하지 않은 노드라면
      if not visited[i]:
        # 삽입, 방문처리
        queue.append(i)
        visited[i] = True

for i in range(1, n + 1):
 # 해당 정점이 방문하지 않았다면
  if not visited[i]:
    bfs(i)
    res += 1

print(res)