[baekjoon] 백준 11724번 : 연결 요소의 개수 (by python) dfs,bfs

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

11724번: 연결 요소의 개수

 

정답 code

-DFS풀이

#연결 요소의 개수
import sys
sys.setrecursionlimit(5000)
input = sys.stdin.readline

#dfs풀이
def dfs(x):
    visited[x] = True

    for i in c[x]:
        if not visited[i]:
            dfs(i)


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

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

cnt = 0

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

print(cnt)

 

-BFS 풀이

#연결 요소의 개수
import sys
sys.setrecursionlimit(5000)
input = sys.stdin.readline

#bfs풀이
from collections import deque
def bfs(n):
    queue = deque([n])
    visited[x] = True

    while queue:
        x = queue.popleft()
        for i in g[x]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

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

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

cnt = 0

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

        else:
            cnt += 1
            bfs(i)
    
print(cnt)

 

solution

bfs나 dfs를 이용해 풀 수 있는 문제다.

다만 연결 요소가 끊어져 있는 경우도 있음으로 bfs나 dfs를 진입하기전에 모든 요소에대해 방문한 요소인지 확인후,

방문하지 않은 요소이고, 이어진 요소가 있다면 bfs나 dfs를 이용해 이어진 요소를 방문처리해준다.

만약 방문하지 않은 요소이지만 이어진 요소가 없다면 count만 하고 넘어간다.(한개의 연결 요소의 개수)

 

한가지 수행이 끝날때마다 count(cnt)를 해주어 연결 요소의 개수를 확인한다.