큐의 활용: 버퍼(Buffer)
일시적으로 데이터 보관하는 메모리의 영역
버퍼링 : 버퍼 활용 방식 또는 버퍼를 채우는 동작
- 자료구조
입출력 및 네트워크와 관련된 기능에서 이용
순서래도 입/출/전달되어야 하므로 FIFO 방식의 자료구조 큐가 활용
큐를 이용한 시뮬레이션
줄서있던 사람이 다시 나가서 뒤에서 줄을 서고 나면 새로운 사람이 들어온다
📍 BFS
-
그래프 탐색하는 방법은 크게 두 가지
깊이 우선 탐색 (DFS)
너비 우선 탐색 (BFS) -
너비 우선 탐색은 탐색 시작점의 인접한 정점을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점을 차례로 방문하는 방식
-
인접한 정점에 대해 탐색 후, 다시 너비 우선탐색을 진행해야 하므로 선입선출 형태의 큐를 활용함
-
탐색순서
A / B, C, D / E, F, G, H, I
BFS 알고리즘
입력 파라미터 : 그래프 G와 탐색 시작점 v
[초기 상태]
visited 배열 초기화 (중복 방지용)
Q 생성
시작점 enqueue
[A점부터 시작]
dequeue: A
A 방문한 것으로 표시
A의 인접점 enqueue
[탐색 진행]
dequeue: B
B 방문한 것으로 표시
B의 인접점 enqueue
dequeue: C
C 방문한 것으로 표시
C의 인접점 enqueue
dequeue: D
D 방문한 것으로 표시
D의 인접점 enqueue
BFS 알고리즘
입력 파라미터: 그래프 G와 탐색 시작점v
시작점이 인큐되었음을 먼저 표시
큐가 안비어 있으면 첫번째 원소 반환
t랑 인접인 애들을 차례대로 꺼내면서
큐에 들어간 적이 없는 애라면
걔를 큐에 넣어주고 큐에 넣었다고 표시
True라고 표시하지 않고 다르게 표시
visited는 원래 주어진 정점 개수만큼만 만들면 된다
*큐에서 꺼내면 방문 안했다고 되어있으니까 방문 표시
빨리가는 선을 기준으로 시간 측정 가는 C는 1분
시간대별로 연락받는 인원도 알 수 있다
각 줄 마다 1분씩 추가
