최단 거리 BFS 문제

다음 그림과 같은 그래프가 있을때 정점(1)에서 출발하여 각 노드들에 도달하는데 걸리는 최단 거리를 출력하는 코드를 구현해 보자!

높이를 나타내서 다시 그려보면 다음과 같다

다음과 같이 dis라는 배열을 만들어 정점 1로부터 도달하는데 걸리는 거리를 하나씩 넣는다.
예를들어 1->4->6->2의 구현과정을 먼저 보자면
dis[4]=dis[1]+1 // dis[4]=0+1=1
dis[6]=dis[4]+1 //dis[6]=1+1=2
dis[2]=dis[6]+1 //dis[2]=2+1=3

우선 BFS를 구현할 ArrayList를 만들어 정점과 간선 정보를 입력한다.

dis 1차원 배열을 머리속에 그리면서 생각하면 도움이 되는 것 같다.