최단경로 (4) 썸네일형 리스트형 가장 먼 노드 - 파이썬 문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 nvertex.. 백준 9370 미확인 도착지 - 파이썬 문제. 풀이. 출발지 s, 경유지 g, h 도착지 d 라고 한다면 두가지 경우의 수 가존재한다. s -> g -> h -> d s -> h -> g -> d 이 2가지를 체크하여 s -> d의 최단경로 거리랑 같다면 정답지에 추가한다. 소스코드. import sys import heapq def dijkstra(start): dp = [100000000 for i in range(n+1)] dp[start] = 0 heap = [] heapq.heappush(heap, [0, start]) while heap: now_weight, now = heapq.heappop(heap) if dp[now] < now_weight: continue for next, weight in graph[now]: next_.. 백준 1504 특정 최단 경로 - 파이썬 문제. 풀이. 저번 포스트에서 풀었던 다익스트라 알고리즘에서 거쳐야하는 정점들이 추가되었다. 우선 시작 정점, v1, v2정점의 최단경로들을 구하고 start -> v1 -> v2 -> end start -> v2 -> v1 -> end 중에서 짧은 경로를 출력하면된다. 소스코드. import sys import heapq def route(start): dijkstra = [INF] * V heap = [] dijkstra[start] = 0 # 시작하는 정점 가중치는 0으로 heapq.heappush(heap,[0, start]) # 우선순위 큐에 가중치과 시작 정점 삽입 while heap: now_weight, now = heapq.heappop(heap) # 현재 테이블과 비교하여 더 가중치가 .. 백준 1753 최단경로 - 파이썬 문제. 풀이. 다익스트라 알고리즘을 숙지하고 있어야한다. https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전 컴퓨터 과학에서, 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. ko.wikipedia.org 다익스트라 알고리즘을 알지못한다면 위의 링크를 참조하면된다. 다익스트라 알고리즘은 모든 플로이드 와셜 알고리즘과 달리 해당 정점에서 모든 정점까.. 이전 1 다음
