BFS2 BFS - 너비 우선 탐색 BFS ( Breadth-First Search ) 는 너비 우선 탐색이라는 탐색법이다. 이전에 포스팅한 깊이 우선 탐색과는 다르게 한 노드에 대해서 갈 수 있는 모든 노드에 대한 탐색을 같이 진행하므로 최단 거리를 찾거나 최단 루트를 찾는 문제 등에 자주 쓰이는 알고리즘이다. 모든 노드들에 대해서 한번씩 탐색을 시도하고, 해당 노드에서 탐색 가능한 모든 노드들에 대해서도 탐색을 해야하므로 큐 자료구조를 이용하여 모든 노드들에 대한 탐색을 시도하되, 먼저 탐색해야 하는 목록에 오른 노드들부터 탐색을 할 수 있게끔 구현합니다. 만약 BFS를 마치고, 해당 탐색 루트 중에서 원하는 위치로 이동 가능한 최단루트를 저장해두고 싶다면, 해당 노드로 최단 비용으로 올 수 있는 바로 이전의 노드의 값을 저장하여 손쉽.. 2023. 2. 10. BFS 문제 풀기 -> 미로 찾기 이와 비슷한 문제를 풀어본 적은 있지만 BFS문제라는 생각을 하고서 풀어본건 이번이 처음이다. 해당 문제는 4방향으로 이동 가능한 미로의 길을 따라 움직이며 (M,N)위치에 도달하기까지의 최종 움직인 횟수를 출력하는 문제였다. 그러므로 이동 가능한 모든 좌표에 최단거리를 계산하여 저장하고, (M,N)까지의 최단거리를 출력하게 된다. 자료구조는 큐를 사용하며 큐에 담긴 좌표들을 모두 검색하며 이동 가능한 방향이 이미 방문한 노드가 아니라면 해당 방향에 대한 좌표를 큐에 다시 담고, 해당 방향의 좌표에 대한 최단거리를 저장한다. 이를 재귀적으로 반복하면 최종적으로 모든 이동 가능한 좌표에 대한 최단거리를 저장할 수 있게 된다. 재귀 개념을 이용하여 접근하면서 직관적이게 해당 개념에 대해 알아보고 풀어나갈 수.. 2023. 2. 2. 이전 1 다음