[백준][DFS/BFS] 11724. 연결 요소의 개수 (파이썬/Python)

DFS를 이용한 풀이 방법(재귀 사용)

#DFS로 풀기
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)


def DFS(x):
    visited[x] = True #방문한 곳은 방문처리 해준다.
    for i in graph[x]:
        if not visited[i]:
            DFS(i)


n, m = map(int,input().split()) # n-정점 개수 / m - 간선 개수 
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
cnt = 0

for i in range(m):
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(1, n+1): #0에 아무것도 넣지 않고 사용하지 않기 때문에 1부터 시작한다.
    if not visited[i]:
        DFS(i)
        cnt+=1
print(cnt)

 

#DFS로 풀기
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000) #재귀 땜에 오류가 나는 것을 방지하기 위한 수 제한 모듈 사용

def DFS(x):
    visited[x] = True
    for i in graph[x]: #해당 정점의 연결된 다른 정점을 확인하기 위함
        if visited[i] == False:
            DFS(i)
        


n, m = map(int,input().split())
graph = [[] for _ in range(n+1)] #1부터 쓰는 이유는 정점이 1부터 사용되기 때문
visited = [False] * (n+1)
cnt = 0
for _ in range(m):
    #굳이 정렬해주지 않는 이유는 어차피 재귀로 돌면 다 돌기 때문
    #순서가 굳이 상관 없는 문제이기 때문이다.
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(1,n+1):
    if visited[i] == False:
        DFS(i)
        cnt += 1
print(cnt)

# 위와 아래의 다른 점은 if visited[i] == False: 라고 해주느냐 if not visited[i]: 라고 해주느냐의 차이다. 

# 재귀를 사용하고 있기 때문에 런타임 에러 (RecursionError)가 뜨기 때문에 호출을 몇번으로 제한해주는 모듈 사용

---

BFS를 이용한 풀이 방법(Queue 사용)

#BFS로 풀기
from collections import deque
import sys
input = sys.stdin.readline

def BFS(x):
    q = deque()
    q.append(x)
    while q:
        a = q.popleft()
        for i in graph[a]:
            if not visited[i]:
                q.append(i)
                visited[i] = True


n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]
cnt = 0
visited = [False] * (n+1)

for i in range(m):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

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

#BFS 문제를 풀 때 pop을 쓰지 않고 popleft를 쓰는 이유는 pop이 효율성이 떨어지기 때문이다. pop()함수는 멀티쓰레드를 위해서 만들어진 함수라고 한다. 그래서 popleft()를 사용한다고 함.

# DFS는 1번 노드부터 확인을 한다고 하면 1번에 연결된 노드에서 제일 깊은 부분까지 갔다가 다시 다른 부분을 확인하는 반면

# BFS는 1번 노드부터 확인을 한다고 하면 1번에 연결된 노드를 전부 다 queue에 넣고 확인한다. 

 

 

# 입력 예제 2번을 예시로 들어서 DFS/BFS의 방향을 살펴보자.

# DFS의 경우엔 1 -> 2 -> 3 -> 4 -> 5 -> 6의 순서로 흘러감

# BFS의 경우엔 1 -> 2 -> 5 -> 3 -> 4 -> 6의 순서로 흘러감

# 순서는 처음 대입되는 노드가 무엇이냐에 따라서 달라질 수 있다.(또한 본인은 우선도를 오름차순으로 두어 진행 이에 따라서도 달라질 수 있다!)