[알고리즘] 그래프.. 트리는 뭔가 쉬운데.. 그래프는 좀;;

안녕하세요, 김송아입니다.

금요일이에요, 금요일!!! 악!!!

 

 

 

가만보면.. 글에서 요일마다 텐션이 다르다는 게 혹시 여러분들도 느껴지시나요..?

이렇게 인생을 일희일비 하며 사는 스타일이

 

 

 

맞습니다.

어떡하겠어.. 기쁜데..💕

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 다 공감하실거라 생각됩니다만? @X.com

 

 

저희 엄마가 제 블로그를 들어와보신다고 해서 짤 쓸까말까 고민 엄청했지만 적절해서 쓸 수 밖에 없었따..

엄마 이거 내가 쓴 말 아니야.. 나도 퍼온거야..

 

 

 

-

 

 

지난 아티클 중에  BFS에 대해 우리 원리를 뜯어보기로 했던 거 기억하시나요?

 

오늘 뜯어보려 했는데!!

아무래도 그 전에 그래프에 대한 우리 편견부터 깨야할 것 같아요.

 

 

 

 

 

우선, 그래프가 뭔지부터 다시 한번 제.대.로 생각해보자구요.

그래프.. 뭔가 어려운 느낌인데.. 싶으시죠?😇

 

 

아마 대부분, 그래프보다는 트리🌲🌲🌲가 좀 더 쉽게 느끼실 것 같아요.

 

그 이유부터 생각해보죠.🤔

트리는 주로 이진 트리 (자식 노드가 최대 2개로 한정되는 트리)에 대해 이야기 하잖아요?!

그렇다보니.. 각 노드들이 어디에 위치해 있는지, 인덱싱도 비교적 쉽게 느껴지기 때문이지 않을까 싶어요.

 

 

예를 들어, 부모 노드 인덱스에..

✔️ X(곱하기) 2를 하면 왼쪽 자식 노드이고,

✔️ X 2 +(더하기) 1을 하면 오른쪽 자식 노드가 되니까!

 

제일 간단하게 (공간 성능을 고민하지 않고) 그냥 배열로도 충분히 트리를 구현할 수도 있으니까요!🙈

 

이진 트리 @위키백과

 

 

그렇다보니 트리 순회도 쉽게 생각하시는 것 같구요!!

트리 순회란? 
트리의 모든 노드를 한번씩 방문하는 과정

 

누가봐도 제일 꼭대기에 시작점이 있으니, 꼭대기부터 시작해서

아래 노드들의 인덱스를 계산해서 찾아다니며 방문하면 되니까요!

 

 

 

 

다시 그래프로 돌아와봅니다.

트리와 다르게.. 그래프는.. 이렇게 생겨가지고..

 

@위키백과

 

이거 뭐.. 순회하려면 시작점도 없고.. 체계적으로 나눠져있지도 않아서..

각 노드들 찾아가려 했는데.. 인덱싱도 안되어 있고..

 

그럼.. 그래프는 어떻게 바라봐야 쉬울지! 같이 생각해봐야겠네요.

 

 

 

다들 알면서, 사실 간과하고 있는 점부터 다시 생각해보면 됩니다.

 

사실 트리는 그래프의 일종이라는 겁니다!!!💡

트리는 시작 노드가 있고, 순환이 없는! 그.래.프!!

 

 

이렇게 되면, 그래프 순회가 조금 쉽게 보이실겁니다!!

 

그래프 순회라는 말! 뜯어볼게요.

Graph Traversal, 그래프의 모든 노드들을 방문하는! 즉, 그래프 완전 탐색입니다.

 

 

그 중에서도 너비 우선 탐색을 콕 찝어서 생각해볼게요.

 

너비 우선 탐색은 그래프를 깊게 내려가는 것이 우선이 아니라

즉, 층을 내려가는 것이 우선이 아니라!!!

같은 층에 있는 노드들을 먼저 모두 탐색하는 것이 우선인 알고리즘입니다.

 

 

 

그래프가 트리도 아니고! 층이 어디있어? 라는 생각이 드시나요?🤔

 

@핀터레스트 박차장님

 

 

트리가 층을 가질 수 있었던 이유는, 다름 아닌 루트 노드가 있기 때문입니다.
루트 노드가 있어서 층이 있다고 할 수 있게 된거였어요!!

 

 

근데.. 그냥 그래프는 트리가 아니라서.. 루트 노드가 없는데..? 싶으실거에요.

 

 

그럼 이건 어떨까요?
그래프에 우리가 임의로 시작 노드를 찍어보는거에요!!📌

 

어떤 노드이건 시작 노드를 잡는다면,

그 시작 노드로부터 간선 하나로 갈 수 있는 노드들이 다음 층이 될 수 있겠죠.

 

 

그리고 그 다음은? 

다음 층으로 넘어가겠다는 뜻을 가지고 있습니다.

 

그래프의 한 노드에서 시작해서

인접한 노드들을 먼저 탐색한 후

그 다음 인접한 노드를 탐색하는 '그래프 완전 탐색' 알고리즘입니다.

 

 

어떠신가요?!

 

 

이제 다 왔어요.

이대로 구현만 하시면 되겠네요 :)

 

그럼, 다음주 화요일 챌린지 글로 BFS 알고리즘 코드로 찾아뵙겠습니다.

 

감사합니다!!

한주 너무너무 고생 많으셨습니다!!! 해피 금요일 되세요!!!