너비 우선 탐색(BFS, Breadth-First Search)BFS는 그래프 탐색 알고리즘 중 하나로, 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘이다. BFS는 최단 경로를 찾는 알고리즘으로도 많이 쓰이곤 하는데, 시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문이다. 쉽게 말해 문제에 대한 답이 많은 경우 너비 우선 탐색은 이 답 중에서도 가장 가까운 답을 찾을 때 유용하다. BFS는 주로 FIFO(선입선출) 방식인 큐 자료구조를 사용하여 구현한다.인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.(DFS는 이와 반대로 스택을 통해 구현한다.) BFS 작동 원..

깊이 우선 탐색(DFS, Depth-First Search)DFS는 그래프 탐색 알고리즘 중 하나로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하여 차례대로 탐색하는 알고리즘이다. DFS는 주로 스택(Stack)을 통해 구현하거나, 재귀문을 통하여 구현한다.DFS 작동 원리1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리를 한다.3. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.4. 2 ~ 3번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.   DFS의 작동원리를 이해하기 위해 아래 사진을 준비..