백준 11724번 파이썬 문제풀이(큐와 그래프 - 연결 요소의 개수) - DFS, BFS

---

이문제는 간단히 연결된 노드들을 간선을 따라 dfs 혹은 bfs로 돌면서 방문한 노드들은 방문기록을 남기면 된다. 간선을 따라 연결된 노드들을 다 돌고 나서 dfs 나 bfs를 한번 빠져나올 때마다 카운트를 1씩 증가시켜서 총 몇번도는지만 체크하면 되는 문제이다.

예를 들어) 위 문제에서 예제 입력 1과 같은 경우 1번 노드부터 dfs를 돈다고 했을 때 1,2,5 노드를 방문하게 되고 visited[1],visited[2],visited[5] 값들을 True로 바꿔주고 dfs를 빠져나오게 된다. 그렇게 빠져나왔을 때 count값을 +1 해주고 이제 이 후 2,5 노드 에서는 dfs를 시작할 일이 없다. 따라서 3노드 에서 dfs를 돈다고 했을 때  3,4,6 노드를 방문하게 되고 똑같이 visited[3],visited[4],visited[6] 값을 True로 바꿔주고 dfs를 빠져나온다. 똑같이 Count 값도 +1 하게 되어 2가 된다. 이제 visited[1] ~ visited[6] 까지 모두 True가 되었기 때문에 dfs를 돌 필요가 없으므로 정답은 2가 된다. 

 

1. DFS

import sys

sys.setrecursionlimit(5000)
input = sys.stdin.readline


# dfs로 그래프를 탐색한다.
def dfs(start, depth):

    #해당 노드 방문체크 한다.
    visited[start] = True

    # 해당 시작점을 기준으로 계속해서 dfs로 그래프를탐색한다.
    for i in graph[start]:
        if not visited[i]:
            dfs(i, depth + 1)


N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 방문처리
visited = [False] * (1 + N)
count = 0  # 컴포넌트 그래프 개수 저장

# 1~N번 노드를 각각돌면서
for i in range(1, N + 1):
    if not visited[i]:  # 만약 i번째 노드를 방문하지 않았다면
        if not graph[i]:  # 만약 해당 정점이 연결된 그래프가 없다면
            count += 1  # 개수를 + 1
            visited[i] = True  # 방문 처리
        else:  # 연결된 그래프가 있다면
            dfs(i, 0)  # dfs탐색을 돈다.
            count += 1  # 개수를 +1

print(count)

2. BFS

import sys
from collections import deque

input = sys.stdin.readline


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


N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 방문처리
visited = [False] * (1 + N)
count = 0  # 컴포넌트 그래프 개수 저장

# 1~N번 노드를 각각돌면서
for i in range(1, N + 1):
    if not visited[i]:  # 만약 방문하지 않았다면
        if not graph[i]:  # 만약 그래프가 비어있다면
            count += 1  # 개수 1개 추가
            visited[i] = True  # 방문 처리
        else:  # 만약 그래프가 비어있지 않다면(어느 점과 연결된 점이 있다면)
            bfs(i)  # 해당 i를 시작노드로 bfs를 돈다.
            count += 1  # 연결요소 를 +1개 해준다.

print(count)