DFS와 BFS에 대한 생각 (뇌피셜)

저는 DFS랑 BFS를 쓰는 문제를 딱 하나씩만 풀어봤고 이사람이 하는 말은 아무 공신력이 없습니다.

DFS BFS를 이제 다음주차에 배울텐데, 느낌이 휘발되지 않도록 다음 주차를 위해 기록해둡니다.

 

DFS의 재귀가 for와 if의 합성으로 자기 자신을 다시 명령하는 방법으로 이루어진다면,
BFS는 queue라는 list의 원소를 태우며 작동하는 while문의 끝에 새 땔감을 추가하는 방식으로 이루어진다.

DFS는 재귀 사이클보다 우선적으로 주어진 if문에 의해 주어진 목표를 만족함을 감지하면 반복을 마치고,

BFS는 while queue문이 할일을 다 끝내서 결과적으로 헛돌면서 재료만 태우다가 queue가 빈 리스트가 되면 반복을 마친다.

DFS는 컴퓨터가 코드를 위에서부터 차례대로 실행하는 특성상 하나의 주문을 마치면 그 과정에서 for문에 의해 새로 끼어든 주문을 처리하러 가고, 미리 정해둔 순서에 따라 for i에서 더이상 파생 주문이 없으면 i+1으로 넘어간다.
BFS는 새로운 땔감이 queue list의 맨 끝에 추가되기에 그래도 미리 들어온 주문은 다 끝낸 다음 새로 파생된 주문을 처리한다. 시작점만 정해주면 현위치의 인접한 곳으로 재귀가 뻗어간다.

 

하나의 일 A를 처리하는 과정에서 새로 A'이라는 일이 생겼다면 옆에 포스트잇을 붙여두고,
A를 마치면 붙어있던 포스트잇을 보고 A'의 일을 처리한다.
A'을 처리하다 A''이라는 일이 생기면 또 포스트잇을 붙인다.
더이상 기존의 일 A에 관련된 포스트잇 A'''''''...이 없다면 그제서야 새로운 일 B를 시작한다.
B에 대해서도 B', B'', ...B''''까지 다 해서 더이상 할게 없으면 이제 C를 하러 간다.
이걸 반복하는게 DFS

하나의 일 A를을 처리하는 과정에서 새로 A'라는 일이 생겨도, A를 마치면 B를 하러 간다.
B를 하다가 B'이 생겨도, B를 마치면 C를 하러 간다.
이걸 반복하다가 ... X, Y, Z까지 원래부터 있던 일을 전부 다하고 나면, 그제서야 아까 A에서 파생된 A'라는 일을 한다.
A'을 하다가 A''이 생겨도 마찬가지로 일단 미뤄두고 B'를 하러 한다.
이걸 반복하는게 BFS

DFS는 내가 평범하게 일을 해결하는 방식과 비슷해서 직관적으로 이해가 가는데

BFS는 이게 어떻게 작동하는건진 알겠어도 왜 이런식(?)으로 일을 벌이는지 잘 모르겠다...

적어도 나는 BFS보단 DFS에 손이 잘 간다...