문제
코드
# 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 증가시켜서 연결 요소의 개수를 구합니다.
