[BOJ](python) 연결 요소의 개수

berry ·2022년 7월 26일
0

Algorithm

목록 보기
77/77
post-thumbnail

🧩 문제

연결 요소의 개수


🧩 문제 해석

📌 연결 요소(Connected Component)

위 그래프를

  • 두 개의 그래프
  • 두 개의 연결 요소를 가진 하나의 그래프

로 볼 수 있다.

📌 연결 요소가 될 조건

  • 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
  • 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

문제에서는,

주어진 노드와 간선들을 모두 하나의 그래프로 보고
연결 요소가 몇 개인지 확인하는 것이다.


🏁 풀이


from collections import deque 

def bfs(graph, v, visit):
    que = deque([v]) # 현재 노드의 연결 요소 계산
    visit[v] = True # 현재 노드 방문
    while que: # 현재 노드와 연결된 노드를 전부 확인할 때까지
        v = que.popleft() 
        for i in graph[v]: # 연결된 노드 중에서
            if not visit[i]: # 연결된 노드가 방문하지 않았다면
                que.append(i) # que에 다음 방문자로 지정(이 노드와 연결된 노드 확인하기 위해)
                visit[i] = True # 방문

n, m = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2) 
    graph[v2].append(v1) # 연결된 노드 저장
visit = [False] * (n + 1)
cnt = 0

for v in range(1, n + 1):
    if visit[v]: continue
    bfs(graph, v, visit)
    cnt += 1

print(cnt)

profile
Engineer

0개의 댓글