BFS

그래프 탐색의 한 방법

그래프 탐색: 어떤 것(Vertex)들이 연속적으로 이어질 때(Edge), 모두 확인하는 방법

그래프 탐색의 종류

• BFS (Breadth-first Search): 너비 우선 탐색
  자기 자식을 우선으로 탐색함

• DFS (Depth-first Search): 깊이 우선 탐색
  자식의 자식을 우선으로 탐색함

아이디어

문제를 어떻게 풀 것인지 설계하고 진행하기

1. 시작점에 연결된 Vertex(자식) 찾기
2. 찾은 Vertex를 Queue에 저장
3. Queue의 가장 먼저 것 뽑아서 반복

데이터 임시 저장소
Stack

• 데이터 입출력 순서 : LIFO(Last In First Out), 후입선출 방식 => DFS
  Queue
• 데이터 입출력 순서 : FIFO(First In Fist Out), 선입선출 방식 => BFS

시간 복잡도

내가 설계한 방법이 오래 걸리는지 확인

알고리즘이 얼마나 오래 걸리는지
가장 최대의 시간을 뽑는 것

• BFS: O(V+E) => Vertex 개수 + Edge의 개수
  

1 > a > b > 2 > 5 > c > d > f > 3 > 4 > e > g > 6

자료구조

내가 자료구조를 어떻게 사용할지 미리 계획
숫자의 경우 최대 자리에 따라서 데이터 타입 예상

1. 검색할 그래프
2. 방문 여부 확인 (재방문 금지)
3. Queue: BFS 실행

---

예제 - 백준 1926 그림

아이디어

• 1번이 나왔을 때 주변의 연속되어 있는 1번들을 계속 찾아 나간다 => BFS
  1인 경우만 찾아나가고, 0인 경우는 찾지 않는다.
• 이중 for문을 사용해 1이 나올 때마다 BFS를 한다.
  ⚠️ 값이 1이고 방문한 적이 없는 곳만 찾아야 한다
  전체 진행하다 1을 발견하면 그림 개수 + 1, 최대값 갱신해주기

시간복잡도

• BFS: O(V+E)
• V: m n (가로 세로)
• E: V * 4(최대 가능한 엣지 값)

=> O(V + E) = V + E = V + 4V = 5V = 5 m n
m, n은 각각 최대값이 500이므로 5 * 250,000 = 약 100만
=> 1초에 연산 2억 개 할 수 있으므로 100만 < 2억 풀이 가능

자료구조

• 그래프 전체 지도: int[][]
• 방문 여부: bool[][]
• Queue(BFS)