[프로그래머스 python]그래프 가장 먼 노드
2020-04-04https://programmers.co.kr/learn/courses/30/lessons/49189
| n | vertex | return |
|---|---|---|
| 6 | [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] | 3 |
노드를 어떻게 돌아야 하는가 부터 고민했다. 문제에서 주어진 간선들을 리스트에 넣었을때
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| [2, 3] | [1, 3, 4, 5] | [1, 2, 4, 6] | [2, 3] | [2] | [3] |
표와 같이 이동 할 수 있고 이를 이용해서 1부터 출발하는 모든 거리를 구해서 그중에 가장 큰것이 몇개 들었는지 count하면 문제가 풀리겠다 생각하고 시작을 했다.
단순히 모든 노드를 돌면 되겠거니 생각하고 재귀를 이용한 dfs를 했더니 도무지 답이 구해지지 않았고 스택이 터지기도했다.
최단경로를 구해야할때는 bfs를 이용해야한다. bfs는 원하는 답을 얻었을때 바로 빠져나올수 있는 반면 dfs는 답을 찾아도 중간에 빠져나오는게 쉽지 않다.
def bfs(v, visited, adj):
count = 0
q = list([[v, count]])
while q:
# print(v, visited, adj,q)
value = q.pop(0)
v = value[0]
count = value[1]
if visited[v] == -1:
visited[v] = count
count += 1
for e in adj[v]:
q.append([e, count])
def solution(n, edge):
node = [[] for _ in range(n + 1)]
dist_list = [-1] * (n + 1)
for e in edge:
node[e[0]].append(e[1])
node[e[1]].append(e[0])
bfs(1, dist_list, node)
return dist_list.count(max(dist_list))
https://dailyheumsi.tistory.com/124