가장 먼 노드

프로그래머스: 가장 먼 노드(파이썬, BFS)

그래프의 root node로부터 가장 멀리 떨어진 노드들의 개수를 구하는 문제이다. 문제의 조건에서 가장 멀리 떨어진 노드의 정의에 대하여 최단경로로 이동했을 때, 간선의 개수가 가장 많은 노드라 명시하였다. 그래프의 탐색이기에 우선 그래프를 인접 행렬로 표현하였고 그 다음으로 그래프의 탐색방법인 DFS, BFS중 고민하였는데 BFS로 푸는 것이 더 효율적이라는 생각이 들었다. 왜냐하면 DFS는 모든 경로를 전부 탐색하여 비교하기에 BFS보다 시간복잡도측에서 비효율적이기 때문이다. 일반적으로 그래프를 탐색하거나 간선들의 가중치가 모두 같을 때 최단경로를 구한다면 BFS가 효율적이다. 혹은 DP를 쓰던지.. 따라서 BFS로 문제를 풀었다. 기본적인 BFS 구현 코드를 사용하였고 거기에 queue에 자식 노..