[백준] 11724번 연결요소의 개수

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

연결요소

나누어진 각각의 그래프를 연결요소라고 한다.
연결 요소를 구하는 방법은 DFS 혹은 BFS탐색을 이용하면 된다.

첫 번째 풀이 : DFS 인접 리스트 사용

import sys
sys.setrecursionlimit(10000) # 1000개 이상의 재귀는 파이썬에서 기본적으로 제한하기 때문에 제한을 풀어줘야 함

N, M = map(int,sys.stdin.readline().split())

nodes = []

for node in range(N+1):
    nodes.append([])

for _ in range(M):
    [v1, v2] = map(int,sys.stdin.readline().split())
    nodes[v1].append(v2)
    nodes[v2].append(v1)

def dfs(ans, i):
    if dfsCheck[i] == 1:
        return
    else:
        ans.append(i)
        dfsCheck[i] = 1
    for path in nodes[i]:
        if dfsCheck[path] == 0:
            dfs(ans, path)

dfsCheck = [0] * (N + 1)
answer = 0

for start in range(1,N+1):
    if dfsCheck[start] == 0:
        answer_path = []
        dfs(answer_path, start)
        answer += 1

print(answer)

두 번째 풀이 : DFS인접 행렬 사용

import sys
sys.setrecursionlimit(10000)

N, M = map(int,sys.stdin.readline().split())

nodes = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    i, j = map(int, sys.stdin.readline().split())
    nodes[i][j] = 1
    nodes[j][i] = 1

dfsMatrixCheck = [0] * (N + 1)

def dfs_for_matrix(ans, i):
    if dfsMatrixCheck[i] == 1:
        return
    else:
        dfsMatrixCheck[i] = 1
    for path in range(1, N+1):
        if dfsMatrixCheck[path] == 0 and nodes[i][path] == 1:
            dfs_for_matrix(ans, path)

ans_matrix = 0
for start in range(1,N+1):
    if dfsMatrixCheck[start] == 0:
        answer_path = []
        dfs_for_matrix(answer_path, start)
        ans_matrix += 1

print(ans_matrix)

세 번째 풀이 : BFS 인접리스트 사용

import sys
sys.setrecursionlimit(10000) 

N, M = map(int,sys.stdin.readline().split())

nodes = []
cnt = 0

for node in range(N+1):
    nodes.append([])

for _ in range(M):
    [v1, v2] = map(int,sys.stdin.readline().split())
    nodes[v1].append(v2)
    nodes[v2].append(v1)

check = [0]*(N+1)
def bfs(n):
    queue = []
    queue.append(n)
    check[n] = 1
    while(queue):
        p = queue.pop(0)

        for node in nodes[p]:
            if check[node] == 0:
                queue.append(node)
                check[node] = 1

for i in range(1,N+1):
    if check[i] == 0:
        bfs(i)
        cnt += 1

print(cnt)