BFS와 DFS 어떻게 활용할까

그래프의 모든 노드를 순회하는 두 알고리즘의 가장 큰 차이는 

1. 동일한 레벨(너비, breadth)의 형제 노드를 먼저 순회하는가 ?(BFS)

2. 깊은(depth) 노드 부터 순회를 하는가? (DFS) 

 

로직 구성은 동일하지만 큐를 쓰는가, 스택을 쓰는가에 따라 순회 순서가 달라진다. 

 

• BFS 코드

from collections import deque

#graph = { 'A':['B'] , 'B':['A','C','D'], 'C':['A','B'], 'D':['A','C'] }

def bfs(graph, start_node):
    visit = []
    queue = deque()

    queue.append(start_node)
    while queue:
        node = queue.popleft()
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node]) #extend는 iterable 형태를 삽입, append는 원소 하나 삽입

    return visit

• DFS 코드 

def dfs(graph, start_node):
    visit = []
    stack = [start_node]
    
    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(graph[node])
    return visit

 

# n개의 정점, m개의 간선, v 시작점 노드 입력이 주어진다.

import sys
read = sys.stdin.readline
m,v,n = map(int, read().split())

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

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

def dfs(v):
    print(v, end = ' ')
    global visit, graph
    visit[v] = 1
    for i in sorted(graph[v]):
    	if visit[i] != 1:
        	dfs(i)

 

 

 

 

DFS 예제 문제 ) 프로그래머스 - 네트워크 

def solution(n, computers):
    answer = 0
    visit = [0] * n 
    
    for cur_com in range(n):
        if visit[cur_com] == 0 :
            dfs(n,computers, cur_com, visit)
            answer += 1 
    
    return answer 

def dfs(n , computers, cur_com , visit):
    visit[cur_com] = 1
    for i in range(n):
        if computers[cur_com][i] == 1:
            if i != cur_com and visit[i] == 0 :
                dfs(n,computers,i , visit)