넘치게 채우기

BFS BFS(Breadth First Search)는 너비 우선 탐색으로, 가까운 노드부터 탐색하는 알고리즘이다. BFS에서는 큐 자료구조를 이용하여 구현한다. 인접한 노드들 중 방문하지 않은 노드를 큐에 추가하면 가까운 노드부터 탐색하는 것이다. 동작 방식은 다음과 같다: 1. 탐색 시작 노드를 큐에 넣고, 방문처리한다. 2. 큐에서 노드를 꺼내 큐의 인접 노드들 중 방문하지 않은 모든 노드들을 큐에 삽입하고, 순서대로 방문처리한다. 3. 2번의 과정을 계속해서 반복한다. 노드 '1'부터 시작해서 '1'을 큐에 넣고 방문처리한다. 노드 '1'을 큐에서 꺼내고, '1'의 인접 노드들 중 방문하지 않은 노드들을 모두 큐에 넣고 방문처리한다. 노드 '2'를 큐에서 꺼내고, 2에 인접한 노드들 중 방문하지 ..

DFS DFS는 Depth-Fisrst Search. 깊이 우선 탐색이다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 자료구조를 사용하고, 최대한 깊숙히 노드를 방문하고, 끝에 도달하면 다시 돌아가서 다른 경로를 탐색한다. DFS 는 다음의 동작과정이 있다: 1. 탐색 시작 노드를 스택에 삽입하고, 노드를 방문처리한다. 2. 스택 맨 위에 있는 노드에서 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고, 방문처리한다. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다. 3. 2번을 계속 방문한다.(스택이 빌 때까지) DFS의 과정 1부터 탐색을 시작한다. 1을 스택에 넣고, 방문처리를 한다. '1'에서 방문하지 않은 인접 노드 '2', '3', '4'가 ..