[백준] 11724번 연결 요소의 개수 파이썬 코드

DFS 코드

 

import sys
sys.setrecursionlimit(10**9) # 재귀 제한 설정
input = sys.stdin.readline

a, b = map(int, input().split())
tree = [[] for _ in range(a+1)]
count = 0 # 연결 요소 개수 세기
visited = [] # 방문 여부 확인
for _ in range(b):
  x,y = map(int, input().split())
  tree[x].append(y)
  tree[y].append(x)

def dfs(v, graph, check_visit):
  check_visit.append(v)
  for i in graph[v]:
    if i not in check_visit:
      dfs(i, graph, check_visit)
# 방문여부에 없으면 (끊겨 있으면) count 추가
for k in range(1,a+1):
  if k not in visited:
    dfs(k, tree, visited)
    count += 1
print(count)

DFS 코드 2

import sys
sys.setrecursionlimit(10**9) # 안해주면 런타임에러 뜸 (RecursionError)
input = sys.stdin.readline

vertex, edge = map(int, input().split())
tree = [[] for _ in range(vertex+1)]
visited = [False] * (vertex+1)

for _ in range(edge):
  x,y = map(int, input().split())
  tree[x].append(y)
  tree[y].append(x)

def dfs(v, graph, check):
  check[v] = True # 방문여부 체크
  for i in graph[v]:
    if visited[i] != True:
      dfs(i, graph, check)

count = 0 # 연결 요소 확인을 위한 변수
for i in range(1, len(visited)):
  if visited[i] != True: # 방문 여부 체크하고 방문이 되어있지 않다면
    count += 1 # 카운트를 늘리고 (연결 요소 개수 증가)
    dfs(i, tree, visited) # 함수 실행
print(count)

리스트에 append 해주는 것과 False를 True로 바꿔주는 방식 속도차이가 많이 난다는 걸 눈으로 확인했다.

 

BFS 코드

 

import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
visited = [False]*(n+1)
cnt = 0
for _ in range(m): # 그래프 만들어주기
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

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

for i in range(1,n+1): # 하나씩 돌면서 방문이 되어있지 않으면 bfs 돌리고 연결 요소 수 1개 증가
    if not visited[i]:
        cnt += 1
        bfs(i, visited)
print(cnt)

 

확실히 dfs가 구현하기에 쉽기는 한 듯.