[백준] 117번 DFS와 BFS 다시 풀기

import sys
sys.setrecursionlimit(10**6)
from collections import deque

N, M = map(int, sys.stdin.readline().split())


graph = [[] for i in range(N+1)]
for i in range(M):
    u,v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

 dfs_visited = [0] * (N+1)
def dfs(V):
    dfs_visited[V] = 1
    for v in graph[V]:
        if not dfs_visited[v]:
            dfs(v)

dfs_count = 0
for i in range(1, N+1):
    if not dfs_visited[i]:
        dfs(i)
        dfs_count += 1

print("dfs_count : ", dfs_count)


bfs_visited = [0] * (N+1)
def bfs(V):
    queue = deque()
    queue.append(V)
    bfs_visited[V] = 1
    while queue:
        startNode = queue.popleft()
        for v in graph[startNode]:
            if not bfs_visited[v]:
                queue.append(v)
                bfs_visited[v] = 1
bfs_count = 0
for i in range(1, N+1):
    if not bfs_visited[i]:
        bfs(i)
        bfs_count += 1

print("bfs_count : ", bfs_count)

그래프의 각 행의 인덱스를 시작노드라 했을 때 그 행의 원소들을 연결된 노드가 되게 만들었다.

DFS

먼저 매개변수로 받은 V를 방문 처리하고, 그 graph의 V행을 돌면서 V와 연결된 노드가 방문되었는지 체크한다. 만약 방문하지 않았으면 dfs를 수행한다.

BFS

매개변수로 받은 V를 큐에 넣고, 방문처리한다. 그리고 while문에서 큐에 있는것을 뽑아 startNode로 하고, graph의 startNode행을 돌면서 startNode와 연결된 노드가 방문하지 않았으면 큐에 넣고, 방문 처리한다. 이것을 큐에 더이상 원소가 없을 때까지 반복한다.

 

메서드 밖 for문에서는 visited 배열을 돌면서 방문처리가 되지 않았으면 dfs나 bfs를 수행하도록하고, 하나의 dfs나 bfs 수행이 끝나면 count가 올라가도록하여 연결된 요소의 개수를 구했다.