[Level3] 가장 먼 노드
1672 단어 DFS/BFS다익스트라programmersDFS/BFS
🛠 문제
👩🏻💻 해결 방법
1번 노드에서 각 노드까지의 최단경로를 구하는 문제이므로 다익스트라 알고리즘을 사용했다
소스 코드
import heapq
def solution(n, edge):
graph = [[] for _ in range(n+1)]
for e in edge:
graph[e[0]].append(e[1])
graph[e[1]].append(e[0])
answer = 0
distance = [int(1e9)] * (n+1)
distance[1] = 0
q = []
heapq.heappush(q, (0, 1))
while q:
d, now = heapq.heappop(q)
if distance[now] < d:
continue
for i in graph[now]:
if distance[i] > d + 1:
distance[i] = d + 1
heapq.heappush(q, (d + 1, i))
max_value = max(distance[1:])
for d in distance:
if d == max_value:
answer += 1
return answer
💡 다른 사람의 풀이
from collections import deque
def solution(n, edge):
def bfs():
q = deque()
q.append(1)
while q:
x = q.popleft()
for i in graph[x]:
if visited[i] == -1:
visited[i] = visited[x] + 1
q.append(i)
graph = [[] for _ in range(n + 1)]
visited = [-1] * (n + 1)
for i, j in edge:
graph[i].append(j)
graph[j].append(i)
visited[1] = 0
bfs()
return visited.count(max(visited))
Author And Source
이 문제에 관하여([Level3] 가장 먼 노드), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyunnn/Level3-가장-먼-노드저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)