1번 노드로부터 각 노드들까지의 최단 거리를 구하는데, 이 때 거리가 최대인 노드들의 개수를 구하는 문제이다.
dfs로도 풀 수 있겠지만,
1과 가장 인접한 노드부터 순차적으로 탐색하는 bfs가 가장 먼저 떠올랐다.
graph와 visit는 solution과 bfs에서 모두 사용하기에 static으로 빼두었다. 생각해보니 n도 static으로 빼도 될 것 같다.
bfs의 경우 최대거리가 1에서 2, 3, 4 로 점점 업데이트가 되는데, 그때마다 거기에 해당하는 노드의 갯수 즉 answer를 초기화하는 로직을 추가해 줘야 한다.
이 부분때문에, 이 문제는 dfs보다는 bfs가 더 적합한 것 같다.
코드 :
...