반응형
49189
-
알고리즘) 프로그래머스 Graph, 가장 먼 노드알고리즘/프로그래머스 고득점 Kit 2020. 4. 25. 15:50
프로그래머스 고득점 Kit - Graph 가장 먼 노드 풀이 2020.04.25) 그래프를 이용해 푸는 문제다. 이에 LinkedList와 PriorityQueue(우선순위 큐)를 이용해 BFS로 문제를 풀었다. 마지막 depth의 노드 수를 구하는 것이기 때문에 BFS가 적절하다고 생각됐다. 1. 루트인 1부터 시작해서 연결된 노드를 탐색한다. 2. 우선순위 큐에 depth를 기준으로 정렬해서 BFS 탐색을 할 수 있도록한다. 이때, visit을 남겨서 depth를 설정할 수 있게 도왔다. 3. depth별로 노드의 수를 세면서, depth가 깊어질 때마다 노드의 수를 0으로 초기화 시켜줬다. 4. 마지막 depth에서 while문을 탈출하면서 노드의 수를 센 result가 return될 수 있게 설정..