반응형 Dijkstra5 C++ 다익스트라 개념과 예제-백준 1753번 다익스트라 알고리즘다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘으로, 가중치 그래프에서 한 정점에서 다른 정점과의 최단거리를 구하는 알고리즘 입니다.다음과 같이 주어진 그래프를 인접리스트로 구현합니다. 한 노드에 대해 인접한 정점을 (노드번호, 거리) 튜플로 저장합니다.1 -> (2,8) (3,3)2 -> (4,4) (5,15)3 -> (4,13)4 -> (5,2)5위와 같이 인접리스트를 만든후, 최단 거리리스트를 초기화하고 탐색을 시작합니다.정점 1부터 출발한다고 가정하겠습니다. (INF는 무한대 입니다.)123450INFINFINFINF그 중 거리가 가장 짧은 1을 채택해서 탐색합니다.12345083INFINF1은 이제 탐색했으므로 방문여부 체크하고 다시 탐색하지 않습니다. 1을 제외한 .. 2024. 5. 15. [백준 1504] 다익스트라(Dijkstra) - 파이썬 (Python) 특정한 최단 경로 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a,.. 2022. 10. 14. [백준 1238] 다익스트라(Dijkstra) - 파이썬 (Python) 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다.. 2022. 10. 14. [백준 1916] 다익스트라(Dijkstra) 알고리즘 - 파이썬(Python) 다익스트라 알고리즘 다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘으로, 가중치 그래프에서 한 정점에서 다른 정점과의 최단거리를 구하는 알고리즘 입니다. 다음과 같이 주어진 그래프를 인접리스트로 구현합니다. 한 노드에 대해 인접한 정점을 (노드번호, 거리) 튜플로 저장합니다. 1 -> (2,8) (3,3) 2 -> (4,4) (5,15) 3 -> (4,13) 4 -> (5,2) 5 위와 같이 인접리스트를 만든후, 최단 거리리스트를 초기화하고 탐색을 시작합니다. 정점 1부터 출발한다고 가정하겠습니다. (INF는 무한대 입니다.) 1 2 3 4 5 0 INF INF INF INF 그 중 거리가 가장 짧은 1을 채택해서 탐색합니다. 1 2 3 4 5 0 8 3 INF INF 1은 이제 탐색했으므로 .. 2022. 10. 14. 파이썬(Python) 다익스트라 개념과 예제-백준 1753번 다익스트라 알고리즘 다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘으로, 가중치 그래프에서 한 정점에서 다른 정점과의 최단거리를 구하는 알고리즘 입니다. 다음과 같이 주어진 그래프를 인접리스트로 구현합니다. 한 노드에 대해 인접한 정점을 (노드번호, 거리) 튜플로 저장합니다. 1 -> (2,8) (3,3) 2 -> (4,4) (5,15) 3 -> (4,13) 4 -> (5,2) 5 위와 같이 인접리스트를 만든후, 최단 거리리스트를 초기화하고 탐색을 시작합니다. 정점 1부터 출발한다고 가정하겠습니다. (INF는 무한대 입니다.) 1 2 3 4 5 0 INF INF INF INF 그 중 거리가 가장 짧은 1을 채택해서 탐색합니다. 1 2 3 4 5 0 8 3 INF INF 1은 이제 탐색했으므로 .. 2022. 10. 14. 이전 1 다음
