글 읽기 - STL을 이용한 BFS의 시간복잡도가 궁금합니다.

n*n배열에서 stl의 queue를 이용하여 bfs를 할 경우 시간복잡도가 궁금합니다.

n*n크기의 맵을 모두 탐색하므로 N^2인지 아니면 STL의 queue를 사용하면서 시간복잡도가 더 증가하는 것인지 궁금합니다.

    int next = Q.front();
    Q.pop();
    for(int d= 0; d<4;d++)
    {
        4방향 탐색
        Q.push(새로운 곳);
    }
}

최악의 경우 맵 크기로 알고 있는데요..

stl의 queue를 사용한다고 시간 복잡도가 증가하진 않습니다.

보통 Queue 같은 경우, pop 연산과 push 연산을 많이 쓰는데요.

이 함수들은 O(1)에 동작합니다.

답변 감사합니다 :)

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge