[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- BFS
- BFS의 유형
- Q&A
- 마치며
1. BFS
- BFS(Breadth First Search)
: 다차원 배열에서 각 칸을 방문할 때, 너비를 우선으로 방문하는 알고리즘
원래 BFS는 그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘.
따라서, BFS를 정확하게 이해하려면, 그래프 자료구조에 대해 알고 있어야 함.
여기서는, 다차원 배열에서의 BFS를 중심.
1) 다차원 배열의 BFS의 방법
-
시작하는 칸을 큐에 넣고, 방문했다는 표시를 남김
-
큐에서 원소를 꺼내어, 그 칸의 상하좌우로 인접한 칸에 대해 3번을 진행
-
해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
-
큐가 빌 때까지 2번을 반복
BFS의 시간복잡도는,
방문했다는 표시를 남기기 때문에 모든 칸은 큐에 1번씩만 들어가게 됨.
따라서 시간 복잡도는, 칸이 N개 일 때 O(N).
만약 행이 R개, 열이 C개라면 O(RC).
2) 다차원 배열의 BFS의 구현
우선 utility헤더의 pair라는 STL을 사용할 것.
(BFS를 구현할 때, 큐에 좌표를 넣을 때 사용)
(코드가 커서 '바킹독님의 깃헙 링크'를 참고)
(BFS의 정석적인 구현은, 거의 외우다시피 해야함.)
2. BFS의 유형
1) Flood Fill
어떤 칸과 연결된 영역을 찾는 유형
이중 for문으로 각각의 칸이 BFS의 시작점이 될 수 있는지 체크해주기.
시간복잡도는 칸의 개수. O(NM).
2) 거리 측정
기존 배열을 -1로 초기화하면, 굳이 vis 배열 없이 방문 여부 확인 가능.
3) 시작점이 여러 개일 때
-
거리가 0인 칸들을 큐에 다 추가
-
거리가 0인 칸들에 의해, 거리가 1인 칸들이 큐에 다 추가됨. 마지막으로 거리가 0인 칸들은 큐에서 모두 pop됨.
-
마찬가지로, 거리가 1인 칸들에 의해, 거리가 2인 칸들이 큐에 다 추가됨. 마지막으로 거리가 1인 칸들은 큐에서 모두 pop됨.
-
...
-
즉, 전체적인 큐의 모양을 확인하면, BFS를 돌 때 큐에 쌓이는 순서는 반드시 거리 순인게 됨.
4) 시작점이 두 종류일 때
각각의 종류마다, BFS를 돌리면 됨.
두 종류면, 두 번의 BFS를 돌리기
5) 1차원에서의 BFS
2차원 BFS와 큰 차이 없음.
3. Q&A
-
4. 마치며
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
