BFS의 (가중치가 동일할때)최단경로의 이유?

BFS에대해서 공부를 하다가 

BFS는 가중치가 동일한 경우 각 노드까지의 거리가 최단 경로라고 

설명되어있었다. 그렇다면 왜???? 

 

왜인지는 설명이 안되어있고 단지 최단 경로일 수 밖에 없다는 글만

수두룩 하였다.

 

내가 이런 궁금증을 가지게 된 이유는

애초에 이해가 덜 되어 있다고 생각한다.

 

1 0 0 0 0

0 0 1 1 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

 

빨간 0에서 출발하여 파란 0까지 가는데

1은 벽이라서 지나가질 못한다고 가정을 해보았을때

 

내가 처음에 한 생각을 너비 우선 탐색이니

시작점에서 오른쪽 과 아랫쪽을 탐색한다. 

결국 오른쪽 끝까지 갔을때 더이상 갈 수 없다는 것을 판단하기때문에

오른쪽 까지 가는 경우도 +3 만큼 카운팅이 된다고 생각하였다.

 

하지만 각 시점에서 노드가 큐에 들어간다고 했을때 

각각의 노드들은 결국 자신의 부모노드에서의 +1 이라고 생각을하니

이해가 갔다. 어떤 곳을 찍더라도 그곳은 결국 최단 경로 일 수 밖에 없었다.