#Algorithm
문제 번호
11724번(S2) : 연결 요소의 개수
알고리즘 + 이론
BFS로 탐색 후 set을 이용해 탐색하지 않았던 start_node를 찾아 연결 요소 개수 세기
정답 코드
# 11724번 연결 요소의 개수 S2
from collections import deque
def bfs(start_node, graph):
queue = deque([start_node])
visited = set([start_node])
while queue:
curr_node = queue.popleft()
for next_node in graph[curr_node]:
if next_node not in visited:
visited.add(next_node)
queue.append(next_node)
return visited
N,M = map(int,input().split())
graph = {n+1:[] for n in range(N)}
result = 0
visited = set()
for _ in range(M):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
for i in range(N):
if i+1 not in visited:
visited.update(bfs(i+1,graph))
result += 1
print(result)
느낀점 & 피드백
정석적인 풀이가 아니라는 생각이 강하게 들지만 나도 맞다.
이 글이 도움이 되셨나요?