https://programmers.co.kr/learn/courses/30/lessons/49189
-
flow
간선 가중치를 모두 1이라 생각하면 양수 가중치 쌍방향 그래프가 되서 다익스트라로 1번 노드와 다른 모든 노드간의 최단 거리 값을 구할 수 있다.. 그 중 거리가 가장 큰 노드들의 개수가 답이 되겠지만 약간 비효율적인 것 같아 다른 방법을 생각해보았다.
1번 노드를 기준으로 너비 우선 탐색을 했을 때, 깊이(depth, height) 가 가장 큰 element(node)s 들의 개수가 답이 될 것이다.
구현 했더니 몇몇 테스트 케이스가 시간 초과로 실패가 떠서.. 최대한 효율적이게 짤 방법을 강구해 보았지만 (visited list 도 제거하고, 반복문도 줄이고 이것저것 다해보다가) 2개의 케이스가 끝까지 통과가 안 되서 일단 넘어가기로 했다...
아마 반복문 한번으로 그래프 구조를 어떤 방식으로든(집합이든 그래프든 트리든 뭐든) 구축하고, 그것을 이용하면 통과하지 않을까 생각해 본다. (귀찮아서 안 그랬더니 내 코드는 반복이 좀 많은 것 같긴하다..) -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A9.py
