TIL::0723_연결 요소/boj_11724번

from collections import deque
import sys

input = sys.stdin.readline


def bfs(v, edges, visited):
    q = deque([v])
    visited[v] = True

    while q:
        now = q.popleft()

        for e in edges[now]:
            if not visited[e]:
                q.append(e)
                visited[e] = True


n, m = map(int, input().split())
edges = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)

result = 0
visited = [False] * (n + 1)

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

print(result)

 https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

그래프 탐색:

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지

 

 

너비 우선 탐색(BFS, Breadth-First Search):

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
-> 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것

사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때