반응형 다익스트라3 [Coding Test][Python][Shortest Path] Floyd-Warshall 알고리즘 개념 및 예제 Floyd - Warshall에 앞서 Dijkstra 알고리즘을 먼저 보고 오시면 좋습니다. [Coding Test][Python][Shortest Path] Dijkstra Algorithm(다익스트라) 개념 및 예제1. Dijkstra Algorithm 이란?Dijkstra 알고리즘이란 Weighted Graph에서 시작점과 도착점이 주어졌을 때 최단 경로(Shortest Path)를 찾는 알고리즘이다.시작 Node에서 출발하여 각 Node 까지의 최단 거리를 점진적self-objectification.tistory.com 1. Floyd - Warshall(플로이드 워셜) 알고리즘 이란?Dijkstra 알고리즘은 한 지젬에서 다른 지점까지로 가는 최단거리만 제공하기 때문에, 모든 지점의 최단거리를 .. 2025. 3. 18. [Coding Test][Python][백준] BOJ #1446 지름길 문제)매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D 킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다.어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.세준이가 운전해야 하는 거리의 최솟값을 출력하시오.입력)첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.출력)세준이가 운전해야하는 거리의 .. 2025. 2. 21. [Coding Test][Python][Shortest Path] Dijkstra Algorithm(다익스트라) 개념 및 예제 1. Dijkstra Algorithm 이란?Dijkstra 알고리즘이란 Weighted Graph에서 시작점과 도착점이 주어졌을 때 최단 경로(Shortest Path)를 찾는 알고리즘이다.시작 Node에서 출발하여 각 Node 까지의 최단 거리를 점진적으로 갱신하며 계산한다. 탐색은 "이미 방문한 Node"와 "방문하지 않은 Node"를 구분하여 진행되며, 방문한 Node로 가는 경로 중에서 가장 짧은 경로를 선택해 나간다. 알고리즘 동작 과정1) Adjance List & Priority Queue 사용Priority Queue에 시작 Node 추가우선 순위가 가장 높은(Distrance가 가작 작은) Node 추출방문 여부 확인Distance Update현재 Node에 연결된 Node를 Prio.. 2025. 1. 30. 이전 1 다음 반응형
