Understanding BFS and DFS in Graph Traversal

BFS는 정점의 폭 우선 탐색을 우선시하는 그래프 탐색 방법입니다.

### 그래프 탐색 소개: BFS 및 DFS 설명
* 👋 안녕하세요, 오늘은 코딩 테스트의 첫 번째 시간으로 **BFS(너비 우선 탐색)**를 소개하겠습니다.
* 🌐 BFS는 그래프 탐색 방법 중 하나로, **연속된 정점들을 확인하는 방식**입니다.
* 📊 그래프 탐색의 예로는 **왕을 찾거나 특정 개체의 수를 조사**하는 것이 있습니다.
* 🔍 BFS는 **자식 노드를 먼저 탐색**하고, DFS(깊이 우선 탐색)는 **자식의 자식을 먼저 탐색**합니다.
* 📈 시간 복잡도는 **O(V + E)**로, 여기서 V는 정점의 수, E는 간선의 수를 나타냅니다.
* 📉 **BFS를 구현하기 위해 큐 자료구조**를 사용하며, **DFS는 스택**을 사용합니다.
* 🔧 BFS 문제를 풀기 위해서는 **그래프 구조와 방문 여부를 확인**할 수 있는 자료구조가 필요합니다.
* 📝 오늘은 **BFS를 코드로 구현**해보고, 문제를 해결하는 방법을 함께 학습하겠습니다.

코딩테스트 알고리즘 - 1. BFS

개발자 장고

소개 및 그래프 탐색 개념 설명

코딩 테스트 첫 번째 시간, BFS(너비 우선 탐색) 시작

BFS는 그래프 탐색의 한 방법, 그래프 탐색이란 연속된 요소들을 모두 확인하는 방법

그래프 탐색 예시: 그래프의 요소들을 순차적으로 확인하는 과정

버텍스(Vertex)와 엣지(Edge) 개념 설명

그래프 탐색의 활용 예시: 왕 찾기, 개수 세기 등

BFS(너비 우선 탐색): 너비를 먼저 탐색, DFS(깊이 우선 탐색): 깊이를 먼저 탐색

BFS 탐색 순서: 자기 자식 노드들을 먼저 탐색 후, 다음 자식 노드의 자식 노드들을 탐색

DFS 탐색 순서: 자식 노드의 자식 노드를 먼저 탐색, 자식이 없으면 위로 올라가 다음 자식 노드 탐색

BFS 예제를 통한 탐색 순서 설명

DFS 예제를 통한 탐색 순서 설명

BFS 코드 구현: 연결된 버텍스들을 큐(Queue)에 저장하고, 가장 앞의 값을 꺼내 반복 처리

큐(Queue) 자료구조 설명: FIFO(First-In, First-Out)

스택(Stack) 자료구조 설명: LIFO(Last-In, First-Out)

BFS에서 큐를 사용하는 이유 설명

시간 복잡도: 알고리즘의 실행 시간 측정

시간 복잡도 표기법: 빅오(Big O) 표기법

빅오 표기법: 최대 시간을 기준으로 알고리즘의 시간 복잡도를 간략하게 표현

BFS 시간 복잡도: V(Vertex) + E(Edge)

필요한 자료구조: 그래프 자료구조, 방문 여부 확인 자료구조, 큐(Queue)

기본 문제(10000번, 1926번): 그래프에서 연속된 1의 개수를 세고 최댓값 구하기

BFS 활용 조건: 1인 경우에만 탐색, 0인 경우는 탐색하지 않음

중복 탐색 방지: 이미 방문한 노드는 다시 탐색하지 않음

코드 구현 및 시간 복잡도 분석

코드 구현 전 고려 사항: 아이디어, 시간 복잡도, 자료구조

아이디어: 이중 반복문과 BFS 활용

시간 복잡도 분석: V + E, V는 정점 개수, E는 간선 개수

문제의 V와 E 계산: N x M (정점), N x M x 4 (간선)

최악 시간 복잡도 계산: 약 100만

자료구조: 2차원 배열(그래프), 2차원 배열(방문 여부), 큐(Queue)

코드 최적화: 미리 계산하여 반복문 횟수 줄이기

입력 데이터 처리: 스트림을 이용한 데이터 변환

이중 반복문 구현: y축 우선 순회

BFS 함수 구현: 방문 여부 체크 및 그림 크기 계산

변수 선언: 그림 개수, 최대 크기

큐가 빌 때까지 반복: 큐에서 요소를 꺼내 주변 탐색

주변 탐색: 상하좌우 탐색 및 방문 여부 확인

테스트 코드 실행 및 결과 확인