전체 글 (82) 썸네일형 리스트형 DFS(Depth-First Search) DFS BFS와 같이 탐색에 이용되는 대표적인 알고리즘이다. BFS(Breadth-First Search) 설명 탐색을 위해 사용되는 알고리즘이다. 이름에서 알 수 있듯이, 너비를 우선으로 탐색하기 때문에 단계적인 탐색을 위해 사용된다. 여기서 탐색이란, 대표적으로 그래프에서 정점 방문을 예 seongmok.com 너비를 우선으로 단계적으로 탐색했던 BFS와 달리 DFS는 깊이를 우선으로 탐색하기 때문에 방문하지 않은 이웃 단계를 최대한 깊게 탐색할 수 있는 만큼 하는 것을 목적으로 한다. 예제를 보며 이해해보자. 다음과 같은 그래프가 있다. 정점1에서 출발하여 모든 정점을 탐색하는데, 이때 위 목적을 바탕으로 움직일 것이다. 불필요한 중복 방문을 막기 위해 현재 정점을 방문체크 한 뒤, 이웃한 정점 중.. BFS(Breadth-First Search) 설명 탐색을 위해 사용되는 알고리즘이다. 이름에서 알 수 있듯이, 너비를 우선으로 탐색하기 때문에 단계적인 탐색을 위해 사용된다. 여기서 탐색이란, 대표적으로 그래프에서 정점 방문을 예로 들 수 있다. 또한, 어떤 작업의 처리에 대한 최소 단계 등을 요구하는 문제에서도 사용될 수 있다. BFS를 구현하기 위해선 Queue가 필요하다. Queue는 선입선출으로 동작하기 때문에 가장 먼저 방문했던 단계의 이웃을 우선으로 탐색할 수 있다. 예제 보며 이해해보자. 다음과 같은 그래프가 있다. 정점1에서 시작해 그래프에 존재하는 모든 정점을 방문할 것이고, 한 정점에서 또 다른 정점은 간선을 통해 이동할 수 있다. 이때, 정점1에서 출발하여 각 정점 단계적으로 모두 방문하고 싶다. 단계적인 탐색이 필요하므로, B.. 이전 1 ··· 8 9 10 11 다음
