🍎 🍎

BFS

• [Algorithm] BFS & DFS

  Algorithm 2022. 3. 15. 09:24

  BFS (Breadth First Search) 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 루트 노드 (혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 Queue를 이용하여 구현 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용 시간 복잡도 O(N) BFS 진행 과정 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다. 2. 큐에서 원소를 꺼내서 해당 칸의 상하좌우로 인접한 칸에 대해 다음 3번을 진행한다. 3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다. 4. 큐가 빌 때까지 2번을 반복한다. ⇒ 모든 칸이 큐에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때..

  Read More