[Python/BOJ] 11724. 연결 요소의 개수

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

11724번: 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

풀이

Code(BFS)

import sys
from collections import deque
input = sys.stdin.readline

# 5, bfs 함수 정의
def bfs(node) :
    # 5-1. 큐에 현재 노드 삽입
    queue = deque([node])
    # 5-2. 현재 위치 방문 처리
    visited[node] = True
    # 5-3.
    while queue :
        # 큐에서 위치 인덱스 반환
        node = queue.popleft()
        # 반환된 위치 인덱스와 연결된 노드 확인
        for x in nodes[node] :
            # 방문하지 않은 경우
            if not visited[x] :
                # 방문 처리
                visited[x] = True
                # 큐에 다음 위치 삽입
                queue.append((x))
    return 1
n, m = map(int, input().split())
nodes = [[] for _ in range(n+1)]
ans = 0
# 1. 각 노드에 간선 정보 입력하기
for _ in range(m) :
    s, e = map(int, input().split())
    nodes[s].append(e)
    nodes[e].append(s)
# 2. 방문 여부 설정
visited = [False] * (n+1)
# 3. for문
for i in range(1, n+1) :
    if not visited[i] :
        ans += bfs(i)
# 6. 결과 출력
print(ans)

Code(DFS)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 5. dfs 함수 정의
def dfs(node) :
    # 5-1.
    for x in nodes[node] :
        # 방문하지 않은 경우
        if not visited[x] :
            # 방문 처리
            visited[x] = True
            # dfs 실행
            dfs(x)

n, m = map(int, input().split())
nodes = [[] for _ in range(n+1)]
ans = 0
# 1. 각 노드에 간선 정보 입력하기
for _ in range(m) :
    s, e = map(int, input().split())
    nodes[s].append(e)
    nodes[e].append(s)
# 2. 방문 여부 설정
visited = [False] * (n+1)
# 3.
for i in range(1, n+1) :
    if not visited[i] :
        dfs(i)
        ans += 1
# 6. 결과 출력
print(ans)