DFS와 BFS 비교해보기

DFS(깊이우선탐색)와 BFS(너비우선탐색)

DFS(깊이우선탐색)

Depth First Search로 깊이를 우선으로 탐색한다.

 

- 최대한 내려간 후 더이상 탐색할 노드가 없는 경우 다시 돌아와 옆 노드 탐색

 

BFS(너비우선탐색)

Breadth First Search로 너비를 우선으로 탐색한다.

 

- 깊이가 1인 모든 노드 방문 후 다음 ㅍ깊이의 모든 노드 방문

 

 

백준 1260번 DFS와 BFS 파이썬 코드

def DFS(v):
    global visited
    visited[v] = 1
    print(v, end=' ')
    for i in range(len(arr[v])):
        if arr[v][i] == 1:
            if visited[i] == 0:
                DFS(i)

def BFS(v):
    global visited
    Q = [v]
    visited[v] = 1
    while Q:
        v = Q.pop(0)
        print(v, end=' ')
        for i in range(1, N+1):
            if visited[i] == 0 and arr[v][i] == 1:
                Q.append(i)
                visited[i] = 1

N, M, V = map(int,input().split())
arr = [[0]*(N+1) for _ in range(N+1)]
visited = [0]*(N+1)

for num in range(M):
    st, ed = map(int, input().split())
    arr[st][ed] = 1
    arr[ed][st] = 1
DFS(V)
print()
visited = [0]*(N+1)
BFS(V)