코딩복습장

이번 포스팅은 너비 우선탐색에 대해서 소개하려고 한다. BFS는 DFS와 같이 그래프 탐색의 대표적인 알고리즘이기도 하다. deque를 사용하고 선입선출 형식을 사용한다. 일반적으로 DFS보다 검색속도가 빠르다고 한다. 바로 탐색 과정을 살펴보도록 하자. BFS 방문과정 빨강이 방문완료, 회색이 방문중이라는 표시이다. Root node를 queue에 넣는다. 1을 방문처리 및 삭제한 후 인접노드인 2, 3을 queue에 넣는다. 인접노드 중에 먼저 들어간 2를 방문처리 및 삭제한 후 4, 5를 queue에 집어 넣는다. 이후 3을 방문처리 및 삭제한 후 3의 인접노드인 6, 7을 queue에 추가한다. 남은 4개는 인접노드가 없으므로, 차례대로 방문처리 및 삭제를 진행한다. 따라서..

깊이 우선 탐색(DFS)란 그래프나 트리를 탐색하는 기법 중 하나이다. 시작노드에서 자식의 노드를 순서대로 탐색하는데, 깊이를 우선하여 탐색한다. 깊이를 우선시하여 모든 경우의 수를 탐색하기 때문에 완전탐색 알고리즘에 속하지만보통 특정 조건을 만족할때까지 탐지하도록 만든다. DFS는 주로 반복문이나, 재귀문을 사용하여 구현한다. DFS의 탐색과정DFS의 기본 탐색과정은 특정 점에서 시작하여 역추척(backtracking)하기 전에 나눠지는 지점을 따라가능한 멀리 탐색하는 것이다. 1. 현재노드를 방문한 것으로 표시한다. 2. 방문한 표시가 되어있지 않는 각각의 인접한 지점을 탐색한다. 3. 더 이상 방문하지 않은 정점이 없다면 이전 정점으로 역추적(backtracking)한다. 4. 모든 정점을..