[언그래머] 코테의 한 끗. B.F.S

안녕하세요 여러분!

김송아입니다.

 

 

오늘의 주제는, BFS입니다.

거의 뭐 BTS 급으로 웅장하게 적었네요. 

 

근데 웅장할만 하지^^;;

 

 

Breadth First Search, 너비 우선 탐색입니다.

 

소위 말해, 코테의 장벽이라고 불리는 알고리즘이죠?

지금부터 그 원리를 쉽고 간단하게 파헤쳐봅니다.

 

우선 BFS는 어떤 자료구조에서 할 수 있는 알고리즘일까요?

바로, 그래프 입니다.

 

 

 

보시다시피

그래프의 모~든 노드를 탐색할 때 사용하는 방법입니다.

(다른 방법도 있어요. 맞아요. 깊이 우선 탐색 DFS)

 

 

말 그대로 너비 우선 탐색이기 때문에 깊이보다 너비가 먼저라는 겁니다.

같은 층에 있는 노드들을 먼저 다 보고, 다른 층을 가겠다는 겁니다.

 

 

루트 노드부터 시작해서

✔️ 한 층씩 내려오면서

✔️ 층마다 같이 사는 모든 노드들을 확인하고 내려오는 시스템입니다.

 

즉, 루트 노드에 가까운 층들에 있는 노드들이 "먼저" 처리 되고

아래 층에 있는 노드들이 "다음에" 처리 되어야 하는 알고리즘입니다.

 

 

다시 얘기하면

루트 노드에서부터 내려오면서 먼저 만난 층에 있는 노드들을 먼저 처리하고
다음 층으로 내려가겠다는 겁니다.

 

자, 그럼 질문입니다.
어떤 자료구조가 생각나시나요????

 

@침착맨

 

 

...

 

BFS 문제는 진짜
BFS부터 제대로 짤 줄 알아야 풀기 수월합니다..

 

다른 자료구조처럼 알고리즘을 그대로 활용하는 게 아니라, 

알고리즘 코드를 변형해서 풀어야 하는 거거든요....! (대.동.공.지.진👀)

 

 

 

-

 

그래서 다음주 화요일 아티클은 BFS 원리를 코드로 한땀한땀 설명드릴 예정입니다!

 

그러려면, 주말에 먼저 해보셔야겠죠?

위에서 확인한 저 BFS를 우리는 어떻게 코드로 옮길 수 있을지

 

구글링하지말고,, 지피티 쓰지말고,, 고민해보자구요🙈

 

 

그럼, 이번 한주도 너무너무 고생 많으셨구!!!

우리는 다음주에 뵙겠습니다💕