최단시간문제1 BFS(Breadth First Search) BFS에 대한 이해 - BFS 란, 시작점으로 부터 너비(거리)를 우선으로 탐색을 진행하는 방법이다. - 보통 BFS 알고리즘은 그래프 자료구조나 2,3차원의 배열과 함께 쓰인다. 너비를 우선으로 탐색한다함은 '거리'를 기준으로 가까운 노드부터 탐색한다는 의미이다. 다음과 같은 그래프 자료구조에서 보라색 노드를 시작 지점으로 탐색을 진행할 때, 보라색 노드로 부터 거리가 1인 초록색 노드들을 먼저 탐색하고, 보라색 노드로 부터 거리가 2인 주황색 노드들은 다음으로 탐색한다. 따라서 BFS 탐색 방법을 사용하여 위의 그래프를 모두 탐색하는 경우, 노드 번호를 기준으로 1 -> 3 -> 2 -> 5 -> 4 -> 6 -> 7 을 지나 탐색이 종료된다. BFS의 구현 BFS는 '큐'로 구현하는 것이 일반적이다.. 2022. 1. 10. 이전 1 다음