BFS 패기✊..는 또맞았다

내가 혼자 정리한 거라

신뢰성이 떨어질 수도 있다.

 

 

---

BFS는 

그래프자료구조에서

데이터를 탐색할 때 유용하게 쓰이는 알고리즘이다.

그래프 자료구조는 순차적으로 나열되어 있는 리스트 자료형과 다르게

데이터가 노드간의 연결로 이루어져있다.

이 데이터들은 보통 Tree 형태로 나타낼 수 있다.

 

리스트로 되어있는 데이터,자료들은 대충 어떻게 탐색할지 감이라도 잡히는데

데이터가 



이런 식으로 연결되어 있는 경우도 있거든..

우리는 인간이니까 

🍙 : "데이터가 뭐..1,2,3도 있네 어 얘네끼리 연결되어있네"

이렇게 알 수 있지만

컴퓨터는 1개 ,1개 일일이 탐색해줘야한다.

 

이 때 ! DFS와 BFS라는 알고리즘 , 데이터를 탐색하는 방법을...

이 사람이 발명했다네요

---

 

 

본론으로 들어가보자.

 

BFS와 DFS 가 있는데 본 게시글에서는 BFS를 정리해볼 것이다.

BFS는 "너비우선 탐색"이다.

말그대로 너비...를 탐색한다는 것이다. 

음 귀찮으니 그림 설명 ㄱ

got it?

그러니까, BFS는 맨 처음 root노드를 방문하면, 그와 연결되어 있는 1과 2를 먼저 탐색한다.

2를 탐색한 다음에는 1과 연결되어 있던 3,4를 모두 탐색한다.

그 다음 2와 연결되어 있던 5,6을 모두 탐색한다.

그러면 ! 

0부터 6까지 모두 탐색할 수가 있다.

 

보통... '뭔가 연결되어있는 노드들을 한 번에 탐색하는게 더 효율적일 것 같은데 ..? '싶으면 BFS를 쓴다.

(나는)

 

DFS는 '한놈만팬다' 이런 느낌이다.

맨 첨 root노드부터 탐색 시작 ! ✊가보자고 !


하면

슬렁슬렁 보면 되는데 연결되어있던 1을 탐색했다 ?

그럼 끝장을 본다.

1봤으면 연결되어 있는 3도 본다. 더 볼게 없으면 pop한다.

어? 근데 1은 갔던 데 잖아 ! 

그러면 4를 탐색한다.

이런식.

 

BFS에서는 한 번에 인접노드를 탐색한다고 했지 않는가.

그러니까,

0을 탐색했으면

그 아래 바로 자식노드인 1,2를 한 번에 탐색하는 것이다.

 

1,2를 ,,?

리스트에 담아숴,,?

q = [1,2]

한 놈씩 맨 먼저 들어온 놈부터 뽑아숴 ,,?

탐색해보자

요런 느낌으로 풀면 됨

 

뭘 쓰면 될까용

 

 

바로

 

큐!!

 

입니다.

 

큐가 뭔가요 

First in 

First out

먼저들어온 사람이 먼저 나가는, 

맛집 줄서는 느낌

 

 

그래서 이 BFS 알고리즘을 활용해서 코드를 짤 때는 보통 ... queue를 씁니다.

while도 같이요

리스트에 원소가 하나도 안남아있을 때까지 다 탐색을 해야 하거든요

 

 

 

그리고 팁 하나 더는

이 그래프를 또 컴퓨터에 그리는 방법이 여러가지가있는데

인접리스트랑 이차원배열..표처럼 만들어서 연결된거를 표시하는 방법이 있습니다.

 

고걸로 연결된 데이터들을 입력값으로 받아온 다음,

행별로,

행 안에 원소들을

전부 탐색합니다.

 

문제를 보겠습니다.

오늘 목표

🍙 효율적인 해킹

🏃🏻‍♀️ 도서관

🐻‍❄️ 4연산

을 풀고 

잘거에요.

 

백준1325- 효율적인 해킹

지난 주에 풀다가 결국 다른 사람 거 보고 했어요

시간복잡도 : 

 

 

 

.

.

.

문제는 다음에 하겠습니다. 

풀이 적기가 귀찮다.