문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 최단 경로로 이동했을 때 가장 멀리 떨어진 노드를 구해야 해서 BFS 알고리즘을 사용했습니다. BFS 는 다음에 탐색할 정보를 queue 에 넣기 때문에 depth 의 경우 shortestList 에 따로 저장하고 현재 노드인 curNodeNum 의 depth 에 1 을 더한 값을 nextNode 의 shortestList 에 추가했습니다. BFS 의 특성상 depth 는 증가만 하기 때문에 이미 최단경로의 depth 를 구한 경우에는 저장하지 않도록 했습니다. 최단경로를 모두 탐색하고 최종적으로 shortestList 에 있는 최대값의 개수를 counting 했습니다. 소스 코드 function solution(n, edge) { l..

1. DFS, BFS 그래프 탐색을 위해서는 DFS ( Depth-First Search, 깊이 우선 탐색 ), BFS ( Breadth-First Search, 너비 우선 탐색 ) 를 사용한다. 2. 그래프와 트리 비교 그래프는 노드와 노드를 잇는 (없을 수도 있지만) 간선을 가진 자료구조이며, 그 중 방향성이 있는 비순환 그래프가 트리이다. 3. DFS, BFS 시간복잡도 인접 리스트로 표현된 그래프 : O(N+E) 인접 행렬로 표현된 그래프 : O(N^2) 참고 : [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)