11724번: 연결 요소의 개수

 

풀이

 

dfs 와 bfs로 풀 수 있는 문제입니다.

 

dfs

...

정점의 개수 n 만큼 값을 넣을 필드 리스트와 방문처리를 위한 리스트를 선언합니다.

 

간선의 개수 m 만큼 간선의 양 끝점 u(start)와 v(end)를 graph에 삽입합니다. 

 

1부터 n+1 만큼 반복문을 돌리면서 아직 방문하지 않은 visited[i] = False 인 곳에서 dfs를 호출합니다.

 

visited[v] = True로 방문 처리를 한뒤 graph[v]의 값을 i로 하나씩 빼와서 아직 방문하지 않은 곳이 있다면 dfs를 재호출하고 함수가 종료될때마다 cnt의 값을 1증가 시킵니다. 

...

 

 

bfs

...

정점의 개수 n 만큼 값을 넣을 필드 리스트와 방문처리를 위한 리스트를 선언합니다.

 

간선의 개수 m 만큼 간선의 양 끝점 u(start)와 v(end)를 graph에 삽입합니다. 

 

1부터 n+1 만큼 반복문을 돌리면서 아직 방문하지 않은 visited[i] = False 인 곳에서 bfs를 호출합니다.

 

visited[v] = True로 방문 처리를 한뒤 graph[v]의 값을 i로 하나씩 빼와서 아직 방문하지 않은 곳이 있다면 queue에 i를 삽입하고 함수가 종료될때마다 cnt의 값을 1증가 시킵니다. 

...

 

파이썬 dfs

import sys
sys.setrecursionlimit(1000000)

def dfs(v):
    visited[v] = True
    for i in graph[v]:
        if visited[i] == False:
            dfs(i)

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]

for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    graph[end].append(start)

cnt = 0
for i in range(1, n+1):
    if visited[i] == False:
        dfs(i)
        cnt += 1
        
print(cnt)

 

 

 

파이썬 bfs

from collections import deque
import sys

def bfs(v):
    visited[v] = True
    queue = deque([v])
    
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if visited[i] == False:
                visited[i] = True
                queue.append(i)                

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]

for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    graph[end].append(start)

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