BFS(Breadth-First Search) 너비 우선 탐색 or 레벨탐색

BFS: 너비 우선 탐색

: 시작 노드에 인접한 노드부터 탐색하는 방법
가장 가까이 있는 정점을 먼저 방문 후 나중에 멀리있는 정점 방문하는 방식. 같은 층(level)에 있는 정점들을 다 방문 후 그 다음 층 노드들로 이동

이진 트리 탐색 코드

• 기본 트리 구현 코드
  
  

• BFS 탐색 코드
  

• 실행 결과
  

송아지 찾기 문제 코드

문제 설명: 현재 나의 위치가 s, 송아지의 위치가 e일때 한번에 이동할 수 있는 양은 -1,1,5뿐이다. 이때 몇번만에 송아지의 위치까지 갈 수있는가?

이 그림을 코드로 구현하면 다음과 같다.

• tree 말단 노드까지 가장 짧은 경로의 높이 출력