1. BFS

참고 유튜브

https://youtu.be/ansd5B27uJM?si=4KO_9l65DvV9ju1w

 

그래프 탐색

어떤 것들이 연속해서 이어질 때 모두 확인하는 방법

모두 확인

BFS / DFS

BFS 너비 -- 자기 자식을 우선으로. 자기 자식 다 보고 자식의 자식에게 넘어감

DFS 깊이 -- 자식의 자식을 우선으로. 자기 - 자식 - 자식의 자식 --- 그 다음 자식  ---

BFS

1 2 5 3 4 6 

DFS

1 2 3 4 6 5 

 

BFS를 어떻게 구현할까??

연결된 간선 찾아서 큐에 저장

큐의 가장 먼저 것 뽑아서 반복

 

큐

1 2 3 들어오면

파이프처럼 나와서 1 2 3 순서대로 나감

 

스택

한쪽이 막힌 자료구조

들어오 ㄴ곳으로 나감

1 2 3 들어옴

3 2 1 나감

 

왜 BFS에서 큐를 사용하는가?

1에서 들어오고

--

1 2 5

2 5

5 3

3 4 

보면 1 이 가장 먼저 들어왔는데 1을 확인하고 지워주니까

먼저 들어온 1을 먼저 내보내는 큐의 개념이 잘 맞는 것이다

 

DFS는 스택으로

BFS는 큐로 

 

** 시간복잡도 - Big O에서는?

BFS (V+E)

버텍스 개수+ 엣지 개수

다 방문하기 때문에?

 

자료구조

1. 검색할 그래프

2. 방문여부 확인 (중복값 제외하기 위해)

3. BFS 실행할 큐

 

** 실습

BOJ 1926 

--

안보고 풀기

 

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

여기서 1로 연결된 가로나 세로가 그림이므로

110

011 

 

11

 

1

 

111

111

111

 

이렇게 4개가 그림이다.

근데 왜 이걸 BFS로 풀어야 할까?

모르겠으므로 설명을 듣자

 

---

1 0 로 이루어진 저것은 그래프이다

1이 나왔을 때 주변에 있는 1들을 찾아 나가는 것이다

찾아 나가는 것 --> BFS

왜? 옆의 자식들을 찾아야 하니까 (저걸 그림이라고 생각해보라)

 

한 점에서는 찾는데 그 다음 점은 어디서?

for문을 돌면서 BFS?

 

이중포문을 돌면서 1이 나올 때마다 BFS를 시작

일단 근데 이중포문에서 중요한 건 방문여부를 판단할 수 있어야 한다는 것이다

 

1 발견 시 그림 개수 1 올리고

그림을 구성하는 1의 최대값도 구해야 한다

 

-- 문제 풀기 전에 봐야할 것

1. 아이디어

2. 시간 복잡도

3. 자료구조

 

1. 이중포면 돌면서 

그래프 값 1 + 방문 x BFS

BFS 돌면서 그림 개수 +1, 최대값 갱신

 

2. BFS 

O(V+E)

V = M*N

E = V*4 (대략)

V+E = 5V = 5MN

MN의 최대값은 500*500 

100만 < 2억 --> 가능

 

3. 자료구조

- 그래프 전체 지도 : int[][] // 1과 0으로 이루어져 있음

- 방문 여부: bool[][]

- Queue (BFS)

 

 

--

여기까지 듣고 혼자 해봐야 할 것 같음. 그리고 관련 문제 풀기.