그래프 넓이우선탐색(BFS, Breadth First Search) 알고리즘(java 코드 포함)
알고리즘 문제에서 동적계획법과 함께 단골로 출시되는 것이 그래프 문제이다.그래프 형태의 자료구조로 표현할 수 있는 문제를 해결하기 위한 알고리즘은 여러 가지가 있다.그 중 가장 기본적이면서도 대표적인 알고리즘 기법이 넓이우선탐색(Breadth First Search)과 깊이우선탐색(Depth First Search)이다. 이 중에서 먼저 넓이우선탐색(BFS, Breadth First Search)에 대해 그림으로 알아보고 예제 문제를 자바(java) 코드로 구현해 보자. 위와 같은 형태의 그래프가 있다. 이제 1번부터 시작해서 넓이우선탐색을 통해 모든 정점들을 하나씩 다 방문해 보려고 한다. 넓이 우선 탐색은 처음 시작 정점을 방문한 뒤, 정점에서 인접한 모든 정점들을 우선 방문한다. 방문하지 않은 정점..