1 분 소요

11724번: 연결요소의 개수

문제

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


입력 조건

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.

(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다.

(1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.


출력 조건

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


첫 번째 시도 .

from collections import deque

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

#인접행렬을 만듬.
for i in range(m):
  x,y = map(int,input().split())
  graph[x][y] = 1
  graph[y][x] = 1
#bfs구현
def bfs(v):
  queue = deque([v])
  while queue:
    x = queue.popleft()
    visited[v] = True
    for i in range(n+1):
      if graph[x][i] == 1 and not visited[i]:
        visited[i] = True
        queue.append(i)
       
result=-1
for k in range(n+1):
  if visited[k] == False:
    bfs(k)
    result+=1
print(result)

»intput

6 5
1 2
2 5
5 1
3 4
4 6

»output

2

success

image-20220301210503456


🌝 Thinking

[아이디어]

  1. 모든 노드에서 BFS를 시행한다.

  2. 방문한 노드는 visited 리스트요소가 True가 된다.

  3. 방문되지 않은 곳에서만 BFS를 한다. BFS가 시행될 때마다 result+=1을 한다.

    편의상 추가한 노드 0이 있음으로 result =-1 부터 시작한다

.

.

역시 BFS는 너무 재밌다… 뭔가 짜릿한 맛이 있다.



💡 깨달은 점.

  1. 간혹 위의 문제처럼 모든 노드에 대해서 조사는 하되 방문여부는 공유하는 문제들이 있다.

    다음과 같은 형식을 외워두어야 겠다.

댓글남기기

참고