[백준 알고리즘] 11724번 연결 요소의 개수, 파이썬(python)

11724, 연결 요소의 개수

📁 문제 출처

11724번: 연결 요소의 개수

 

💡 생각

• 방향이 없는 그래프는 graph[a].append(b), graph[b].append(a)로 양방향을 넣어주고 큐에 넣어주면서 모든 노드를 검사하면 된다.
• 쭉 연결이 되어 있다면 bfs함수 한 번에 끝나지만, 연결이 끊기면 다시 돌아와서 bfs 함수 실행하기 때문에 이때 answer를 카운트해주면 된다.

 

🛠 나의 코드

import sys
input = sys.stdin.readline
from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])

    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


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

graph = [[] for _ in range(n+1)]

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

visited = [False] * (n+ 1)

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

print(ans)

 

✔️ 배운 점 및 주의할 점

• 실제 코테에서 직접 입력 받을 일은 없으니까 bfs 함수 부분만 구현하면 된다.