BFS 설명 (1) 썸네일형 리스트형 BFS(Breadth-First Search) 설명 탐색을 위해 사용되는 알고리즘이다. 이름에서 알 수 있듯이, 너비를 우선으로 탐색하기 때문에 단계적인 탐색을 위해 사용된다. 여기서 탐색이란, 대표적으로 그래프에서 정점 방문을 예로 들 수 있다. 또한, 어떤 작업의 처리에 대한 최소 단계 등을 요구하는 문제에서도 사용될 수 있다. BFS를 구현하기 위해선 Queue가 필요하다. Queue는 선입선출으로 동작하기 때문에 가장 먼저 방문했던 단계의 이웃을 우선으로 탐색할 수 있다. 예제 보며 이해해보자. 다음과 같은 그래프가 있다. 정점1에서 시작해 그래프에 존재하는 모든 정점을 방문할 것이고, 한 정점에서 또 다른 정점은 간선을 통해 이동할 수 있다. 이때, 정점1에서 출발하여 각 정점 단계적으로 모두 방문하고 싶다. 단계적인 탐색이 필요하므로, B.. 이전 1 다음
