코딩테스트 bfs (1) 썸네일형 리스트형 [코딩테스트][알고리즘] 6. BFS (Breadth First Search) 너비 우선 탐색 BFS 역시 DFS와 마찬가지로 코딩 테스트에 자주 나오는 유형이다. BFS는 아래 그림과 같이 진행되는 탐색 알고리즘이다. 시작점으로부터 같은 이동거리에 있는 점들 순차적으로 탐색하는 방법이고, 동심원을 그리며 탐색을 하는 것으로 생각할 수도 있다. 시작점으로부터 이동거리 순으로 탐색을 하기 때문에 최단경로를 구하는데 유용하게 사용된다. BFS는 자료구조 Queue를 사용해서 구현할 수 있다. 코딩 테스트를 위한 BFS는 미로와 같이 x, y 좌표를 이용하는 문제에 자주 사용되는 것 같다고 생각되어 미로 문제를 통해 BFS를 어떻게 코드로 표현하는지 알아보려고 한다. bfs의 구현을 말로 설명하자면 다음과 같이 진행된다. 1. 탐색할 위치의 좌표를 queue에 넣고 방문처리 한다. 2. queue에서 .. 이전 1 다음
