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

BFS/DFS를 처음 접하는 사람은 아래 링크의 유튜브 설명을 보는 것을 추천한다.
BFS/DFS를 이해하기 정말 좋은 영상이고, 이 포스팅도 해당영상을 기반으로 했다.

 

▶ 위의 그림은 DFS와 BFS 경로를 순서대로 나타낸 것이다.

해당 그림을 통해 직관적으로 DFS와 BFS의 차이를 알 수 있을 것이다.
깊이우선탐색인 DFS는 가장 깊은 곳까지 방문하고, 너비우선탐색인 BFS는 같은 레벨 인접 노드를 전부 방문한뒤 다음 레벨 인접 노드를 방문한다. DFS는 Stack을 통해 구현하고, BFS는 Queue를 통해 구현한다.

 

✏️ 깊이우선탐색(DFS) 구현

 

👉🏻 깊이우선탐색 DFS(Depth-First Search)는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

▶ 깊이우선탐색(DFS) 구현 방법

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

▶ 해당 그래프를 DFS로 구현해보자. DFS는 Stack을 이용한다. Stack은 한 방향에서만 자료를 넣고 뺄 수 있는 후입선출 방식 구조이므로, 가장 늦게 들어온 노드를 가장 먼저 뺄 수 있다. 또한, 한 번 담았던 노드는 다시 담지 않는다.

▶ 먼저 시작 노드인 0번 노드를 스택에 담았다.

▶ 이 후 0번 노드를 꺼내 출력하고, 그 인접 노드인 1번 노드를 스택에 담았다.

▶ 이 후 1번 노드를 꺼내 출력하고, 그 인접 노드인 2번 노드와 3번 노드를 스택에 담았다.

▶ 이 후 3번 노드를 꺼내 출력하고, 그 인접 노드인 4번 노드와 5번 노드를 스택에 담았다.
    2번 노드는 이미 스택에 담겨있으므로 스택에 다시 추가하지 않는다.

▶ 이 후 5번 노드를 꺼내 출력하고, 그 인접 노드인 6번 노드와 7번 노드를 스택에 담았다.

▶ 이 후 7번 노드를 꺼내 출력하고, 인접 노드가 없으므로 더 담지 않는다.

▶ 이 후 6번 노드를 꺼내 출력하고, 그 인접 노드인 8번 노드를 스택에 담았다.

▶ 이 후 8번 노드를 꺼내 출력하고, 인접 노드가 없으므로 더 담지 않는다.

▶ 이 후 4번 노드를 꺼내 출력하고, 2번 노드를 꺼내 출력한다. 더 꺼낼 노드가 없으므로 순회는 종료한다.

 

DFS 경로 : 0 > 1 > 3 > 5 > 7 > 6 > 8 > 4 > 2

 

💡 출력 순서와 과정은 스택이기 때문에 위와 같이 이루어지는 것이다. 스택은 마치 박스 쌓기와 같아서 가장 늦게 올린 박스를 가장 먼저 꺼낼 수 있다(후입선출). DFS 구현 과정 또한 스택으로 구현하는 것이기에 가장 위에 있는 노드를 계속 꺼내는 것이다.

 

✏️ 너비우선탐색(BFS)

 

👉🏻 BFS(Breadth First Search)는 그래프에서 가까운 노드부터 탐색하는 알고리즘이다.

 

▶ 너비우선탐색(BFS) 구현 방법

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

▶ 해당 그래프를 BFS로 구현해보자. BFS는 Queue를 이용한다. Queue는 가장 먼저 들어온 것이 가장 먼저 나가는 선입선출 방식의 구조이다. DFS 구현과 마찬가지로 한번 큐에 담았던 노드는 다시 담지 않는다.

▶ 먼저 시작 노드인 0번 노드를 큐에 담았다.

▶ 이 후 0번 노드를 꺼내 출력하고, 그 인접 노드인 1번 노드를 큐에 담았다.
    큐는 선입선출이므로 꺼내는 방향이 그림의 화살표처럼 아래부터이다.

▶ 이 후 1번 노드를 꺼내 출력하고, 그 인접 노드인 2번 노드와 3번 노드를 큐에 담았다.

▶ 이 후 2번 노드를 꺼내 출력하고, 그 인접 노드인 4번 노드를 큐에 담았다.

💡 큐는 선입선출 방식이므로 가장 아래 있는 2번 노드부터 꺼낸다. 또한, 그 인접 노드 중 1번, 3번은 이미 큐에 들어갔었으므로 4번 노드만 큐에 담긴다.

▶ 이 후 3번 노드를 꺼내 출력하고, 그 인접 노드인 5번 노드를 큐에 담았다.

▶ 이 후 4번 노드를 꺼내 출력하고, 그 인접 노드는 전부 큐에 담았던 적이 있으므로 다시 담지 않는다.

▶ 이 후 5번 노드를 꺼내 출력하고, 그 인접 노드인 6번 노드와 7번 노드를 큐에 담았다.

▶ 이 후 6번 노드를 꺼내 출력하고, 그 인접 노드인 8번 노드를 큐에 담았다.

▶ 이 후 7번 노드를 꺼내 출력하고, 8번 노드를 꺼내 출력한다. 더 꺼낼 노드가 없으므로 순회는 종료한다.

 

BFS 경로 : 0 > 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8

 

✏️ DFS와 BFS 예제

백준에서 대표문제인 1260번 DFS와 BFS예제가 있다.
아래 링크에 해당 문제와 구현을 자세히 적어놨다.
https://velog.io/@falling_star3/백준Python-1260번-DFS와BFS