[Algorithm] 백준 11724 - 연결 요소의 개수 in Python(파이썬)

💡 백준 11724:

DFS 탐색

🌱 코드 in Python

알고리즘: DFS

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = map(int, input().split())

g = [[] for _ in range(n + 1)]
visit = [0] * (n + 1)
cnt = 0

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

def dfs(i):
    visit[i] = 1
    for j in g[i]:
        if visit[j] == 0:
            dfs(j)

for i in range(1, n + 1):
    if visit[i] == 0 and g[i]: # 아직 방문하지 않았고, 연결된 요소가 있을 경우
        dfs(i) # DFS 진행
        cnt += 1
    if visit[i] == 0 and not g[i]: # 아직 방문하지 않았지만, 연결된 요소가 없을 경우
        cnt += 1 # DFS 진행하지 않고 cnt만 증가

print(cnt)

이번 문제는 연결된 요소의 개수를 구하는 문제로 간단히 dfs를 돌려야 하는 횟수 + 자기 자신만 있는 경우의 수로 구할 수 있는 문제였다
dfs의 standard형 문제여서 그다지 어렵지 않게 풀 수 있었다
딱히 주의할 점은 없었음

🧠 기억하자

1. 이런 문제는 이제 풀 수 있어!

백준 11724 바로가기