프로그래머스, 가장 먼 노드 [파이썬]

[ 문제 설명 ]

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

입출력 예

nvertexreturn

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

 

[ 문제 풀이 ]

이 문제는 풀이 시간이 중요하다. 시간초과로 인해서 문제가 틀리기 때문이다. 

제일 처음 문제를 보았을때 다익스트라나 플로이드 워셜이 떠올랐다. 하지만 출발점이 1로 고정되어있기 때문에 다익스트라로 풀어야지 라고 생각하며 풀이를 진행했다. 

답은 나왔으나 두 경우에 대해서 시간 초과가 발생했다. 

조금 더 최적화가 필요한 부분이었고 질문들을 보면서 생각해보았는데 대부분 dfs나 bfs를 기반으로 접근하고 그에 따른 방문거리정도만 기록했다. 분명한건 dfs보다는 bfs가 빠르며 인접행렬보다는 인접리스트가 빠르다. 

다른건 다익스트라를 썼다는 점인데 그러고보니 bfs나 다익스트라나 구현에 있어서 별로 다를 것이 없었다. 

단지 조건이 달랐다. (방문했는지? vs 거리가 더 작은지?)

이 경우에 방문했는지라고 바꾸었을때 문제가 해결되었다. 왜냐하면 bfs로서 먼저 접근하면 이후 경우보다 빠를수 밖에 없기 때문이다. 

코드는 아래와 같다.