너비 우선 탐색(Breadth-first search, BFS)

너비 우선 탐색이란?

• 분류 : 검색 알고리즘
• 자료 구조 : 그래프(Graph)

 

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 ㅇ낳은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.

 

너비 우선 탐색의 애니메이션

 

의사 코드(Pseudo Code)

def breadth_first_search(problem):

  # a FIFO open_set
  open_set = Queue()
  # an empty set to maintain visited nodes
  closed_set = set()
  # a dictionary to maintain meta information (used for path formation)
  meta = dict()  # key -> (parent state, action to reach child)

  # initialize
  start = problem.get_start_state()
  meta[start] = (None, None)
  open_set.enqueue(start)

  while not open_set.is_empty():

    parent_state = open_set.dequeue()

    if problem.is_goal(parent_state):
          return construct_path(parent_state, meta)

    for (child_state, action) in problem.get_successors(parent_state):

      if child_state in closed_set:
        continue

      if child_state not in open_set:
        meta[child_state] = (parent_state, action)
        open_set.enqueue(child_state)

    closed_set.add(parent_state)


def construct_path(state, meta):
  action_list = list()

  while True:
    row = meta[state]
    if len(row) == 2:
      state = row[0]
      action = row[1]
      action_list.append(action)
    else:
      break

  return action_list.reverse()

 

C# 예제 코드

public void BFS()
{
    int[] dirY = new int[] { -1, 1, 0, 0 };
    int[] dirX = new int[] { 0, 0, -1, 1 };

    bool[,] found = new bool[board.Size, board.Size];
    Pos[,] parent = new Pos[board.Size, board.Size];

    Queue<Pos> q = new Queue<Pos>();
    q.Enqueue(new Pos(PosY, PosX));

    found[PosY, PosX] = true;
    parent[PosY, PosX] = new Pos(PosY, PosX);

    while(q.Count > 0)
    {
        Pos pos = q.Dequeue();

        int nowY = pos.Y;
        int nowX = pos.X;

        for (int i = 0; i < 4; i++)
        {
            int nextY = nowY + dirY[i];
            int nextX = nowX + dirX[i];

            if (nextY <= 0 || nextX <= 0 || nextY >= board.Size || nextX >= board.Size)
            {
                continue;
            }

            if (board.Tile[nextY, nextX] == TileType.Wall)
            {
                continue;
            }

            if (found[nextY, nextX])
            {
                continue;
            }

            q.Enqueue(new Pos(nextY, nextX));
            found[nextY, nextX] = true;
            parent[nextY, nextX] = new Pos(nowY, nowX);
        }
    }

    CalcPathFromParent(parent);
}

private void CalcPathFromParent(Pos[,] parent)
{
    int y = DestY;
    int x = DestX;

    while (parent[y, x].Y != y || parent[y, x].X != x)
    {
        path.Add(new Pos(y, x));

        Pos pos = parent[y, x];
        y = pos.Y;
        x = pos.X;
    }

    path.Add(new Pos(y, x));
    path.Reverse();
}

 

함께 읽으면 좋은 글

Graph 자료구조

그래프(Graph)와 트리(Tree)

[프로그래머스 Programmers] 네트워크