[백준 11724] 연결 요소의 개수(python)

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

11724번: 연결 요소의 개수

연결 요소의 개수 문제

방향 없는 그래프가 주어졌을 때 연결 요소의 개수를 구하는 문제

BFS와 DFS를 이용해서 해결할 수 있었다.

 

📌 문제 접근 포인트

1. 주어진 조건대로 방향 없는 그래프(양방향 그래프)를 구성해 주자.
2. 그래프를 탐색할 수 있도록 BFS나 DFS를 구성하자.
3. 연결 요소의 개수를 구하기 위해서는 방문 표시를 해줄 때, BFS나 DFS를 통해서 탐색을 진행해 주자.
4. 그래프 탐색을 진행할 때마다 방문하지 않은 지점부터 시작하므로, 시작하는 횟수를 세어주면 연결 요소의 개수를 구할 수 있다. 

⚙️내가 푼 정답 코드(BFS)

# BFS 활용
def find(n):
    visited[n] = 1
    queue = deque()
    queue.append(n)
    while queue:
        a = queue.popleft()
        for i in graph[a]:
            if not visited[i]:
                visited[i] = visited[a] + 1
                queue.append(i)   

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
visited = [0]*(N+1)
for _ in range(M):
    u, v = map(int,sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
result = 0
for i in range(1,N+1):
    if not visited[i]:
        find(i)
        result += 1
print(result)

 ⚙️내가 푼 정답 코드(DFS)

#DFS 활용
def find(n):
    global visited
    visited[n] = 1
    stack = []
    stack.append(n)
    while stack:
        a = stack.pop()
        for i in graph[a]:
            if not visited[i]:
                visited[i] = visited[a] + 1
                stack.append(i)   

import sys
N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
visited = [0]*(N+1)
for _ in range(M):
    u, v = map(int,sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
result = 0
for i in range(1,N+1):
    if not visited[i]:
        find(i)
        result += 1
print(result)