[Java] 너비 우선 탐색 BFS 대하여 알아보자

2021-02-11 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. (출처 위키피디아) 사실 말은 조금 어려울 수 있어 그림으로 다시 한번 설명하겠다. 아래의 예제를 보자. BFS로 1번 정점부터 시작해 탐색을 진행해 보겠다. 순서는 아래와 같다. 1 - > 1번 정점이 큐에 들어가게 된다. 2 - > 1번 정점과 인접해 있는 두 개의 접점 2번과 4번 정점을 큐에 담는다. 3 - > 1번 정점과 인접한 곳..