[바킹독의 실전 알고리즘] 0x09강 - BFS
·
Computer Science/자료구조 | 알고리즘
BFS(Breadth First Search) 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 -> 너비 우선으로 방문?? 그래프에서 모든 노드를 방문하는 알고리즘 그래프: 정점과 간선으로 이뤄진 자료구조 예시 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 큐에서 원소 꺼내 그 칸에 상하좌우로 인접한 칸에 대해 3번 진행 해당 칸 이전에 방문했다면 아무것도 하지 않고, 처음 방문했다면 방문했다는 표시 남기고 해당 칸을 큐에 삽입 큐 빌 때까지 2번 반복 => 모든 칸이 큐에 1번씩 들어감 -> 시간복잡도는 칸이 N개일 때 O(N) ex. 행이 R개, 열이 C개 -> O(RC) (0, 0)과 상하좌우로 이어진 모든 파란칸 확인 좌표를 담을 큐 필요 (0, 0)에 방문했다는 표시 + ..
