BOJ/백준-11724-Python

문제

코드

# https://www.acmicpc.net/problem/11724
# boj, 11724: 연결 요소의 개수, python3
from collections import deque
import sys

input = sys.stdin.readline

def bfs(start, visited, graph):  # 무방향 그래프 탐색에서는 BFS(너비 우선 탐색)이 대체로 유리.
    queue = deque([])  # 자료구조 queue 초기화
    queue.append(start)
    visited[start] = True  # 현재 위치 방문처리

    while queue:  # 큐가 빌때까지 반복
        v = queue.popleft()

        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

if __name__ == '__main__':
    n, m = map(int, input().split())  # 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.
    graph = [[] for _ in range(n+1)]  # 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다.

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

    visited = [False] * (n+1)  # 방문처리를 담은 list
    count = 0  # 연결 요수 개수 변수

    for i in range(1, n+1):  # 탐색 수행
        if not visited[i]:
            bfs(i, visited, graph)
            count += 1

    print(count)  # 연결 요소 개수 출력

결과

ChatGPT Code

def dfs(v):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

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

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

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

print(count)

ChatGPT 문제풀이

이 문제는 그래프의 연결 요소의 개수를 구하는 문제입니다. DFS 또는 BFS 알고리즘을 사용하여 그래프를 탐색하면서 연결 요소의 개수를 세어주면 됩니다.
위 코드에서 dfs 함수는 DFS 알고리즘을 구현한 함수입니다. visited 리스트는 방문한 노드를 표시하기 위한 리스트이고, count 변수는 연결 요소의 개수를 저장하는 변수입니다.
그래프는 인접 리스트 형태로 입력받아서 저장하고, 각 노드를 DFS 함수에 전달하여 탐색합니다. 이 때, 이미 방문한 노드는 visited 리스트에 표시하여 중복 탐색을 방지합니다.
탐색이 끝나면 count 변수를 1 증가시켜서 연결 요소의 개수를 구합니다.

출처 & 깃허브

boj 11724
github