[python] 11724, 연결 요소의 개수 : DFS, BFS

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

코드 구현 ) https://github.com/nyunu/BaekJoon/blob/main/11724.ipynb

 

[ 문제 ]

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

 

[ 입력 ]

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

 

[ 출력 ]

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

 

[ 예제 ]

 

[풀이]

DFS와 BFS의 기본적인 구성으로 풀이 가능한 문제이기 때문에 추가적인 풀이는 필요없을 것 같다.

DFS와 BFS에 대한 개념만 사용하면 되는 문제이기에, 풀이는 다음의 글을 참고하면 되리라 생각된다 !

링크) https://nyunu.tistory.com/49

[자료구조] DFS(깊이 우선 탐색) & BFS(너비 우선 탐색) (in python)

 

1. DFS

import sys

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

graph = [[] for i in range(n + 1)]

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

visited = [False] * (1 + n)

def dfs(start, depth):
    visited[start] = True
    for i in graph[start]:
        if not visited[i]:
            dfs(i, depth + 1)

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

print(cnt)

 

2. BFS

from collections import deque
import sys

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

graph = [[] for i in range(n + 1)]

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

visited = [False] * (1 + n)

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

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

print(cnt)