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

백준 11724번

최종 제출 코드

import sys
input = sys.stdin.readline

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

for i in range(m):
  a, b = map(int, input().split())
  graph[a][b] = 1
  graph[b][a] = 1


def bfs(node):

  global cnt
  cnt += 1
  
  queue = [node]
  visited[node] = True
  
  while queue:
    node = queue.pop(0)

    for i in range(1, n+1):
      if graph[node][i] == 1 and visited[i] == False:
        queue.append(i)
        visited[i] = True

for i in range(1,n+1):
  if visited[i] == False:
    bfs(i)

print(cnt)

◼️ bfs를 활용하여 문제풀이

• bfs는 노드를 돌면서 이미 탐색한 노드는 visited 배열을 통해 확인!
• 첫번째 노드부터 방문한 노드인지 아닌지 확인하여, 아직 방문하지 않았을 경우 해당 노드를 기준으로 bfs를 실행한다.
• 연결 요소의 개수를 확인하기 위해 bfs가 호출될 때마다 cnt 변수를 업데이트