알고리즘/BFS (1) 썸네일형 리스트형 BFS(Breadth-First-Search) BFS는 너비 우선 탐색 그래프에서 순회 방법 중 하나이다. 시작 노드에 인접한 노드를 모두 방문하고, 방문한 노드에서 인접 노드를 모두 방문 탐색하는 알고리즘이다. BFS의 동작 과정을 이해하기 위해서는 먼저 그래프 자료구조와 큐 자료구조에 대해 이해할 필요가 있다. BFS 알고리즘은 그래프에서 가까운 노드부터 우선적으로 탐색하는 점에서, 선입선출의 큐(Queue) 자료구조를 활용한다. 인접한 노드를 순차적으로 큐에 삽입하고 (FIFO) 선입선출에 의해 큐를 꺼내도록 알고리즘을 작성하면 된다. BFS의 장단점 BFS의 장점 1. 답이 되는 경로의 최단경로를 찾는다. 2. 무한으로 길어지는 경로의 해답을 찾을 수 있다. BFS의 단점 1. 경로가 길어짐에 따라 메모리 공간을 많이 차지하게 된다. 2. 해.. 이전 1 다음