다익스트라5 [G3] 백준 11779 - 최소비용 구하기 2 (Python3) https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다. 입력 첫.. 2023. 12. 16. [G4] 백준 1504 - 특정한 최단 경로 (Python3) https://www.acmicpc.net/problem/1504 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘.. 2023. 12. 16. [G4] 백준 1753 - 최단경로 (Python3) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 해결방법 다익스트라 알고리즘을 활용하여 풀었다. 풀이👀 나는 그래프를 python의 dictionary로 표현했다. 그래서 입력받은 간선의 정보들을 모두 graph에 담았다. * 하지만 이렇게 되면 쓸모없는 데이터까지 받아오게 된다. "서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다." 라는 문제 조건이 있기 때문이다. 모든 정보를 담.. 2023. 2. 20. [G5] 백준 1916 - 최소비용 구하기 (Python3) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 해결방법 다익스트라 알고리즘을 이용한다. 풀이👀 입력에서 버스 이동에 대한 정보를 제공해주고 있다. 순서대로 [출발점, 도착점, (출발->도착)비용] 이다. 각 지점에서는 연결 된 다른 점들로 이동할 수 있다. 이 이동에서 비용이 발생한다. 그런데 이동을 하면서 출발점과 도착점이 같지만 중간에 우회하는 경로를 달리하여 그 비용(결과)를 저렴하게 할 수 있다. 하지.. 2023. 1. 30. [22동계모각코] 7회 계획 및 평가 시작 시간 : 23-01-30 오후 6시 오늘의 목표 다익스트라(Dijkstra) 알고리즘 공부 이렇게 공부한 알고리즘을 정리해보는 것은 처음이다. 그래서 글이 너무 복잡하고, 정리가 안 되어 있다. 오늘은 다익스트라 알고리즘을 공부했다. 다익스트라 알고리즘은 정보 탐색 중에서 최단 경로를 구하기 위한 알고리즘이다. 정보 탐색이란, 탐색에 필요한 정보들을 탐색 전에 미리 알고 있는 경우이다. a에서 b까지의 이동경로를 직접 가보지 않고 미리 알수 있는 경우가 정보탐색인 것이다. 또 다른 특징이 있다면, 비용(cost)의 정보가 모두 음이 아닌 정수여야 한다. 비용 정보가 음수도 포함이 된다면 '플로이드-워셜' 알고리즘으로 해결해야 한댔다. *논외이긴 하지만 정보가 사전에 준비되지 않은 경우에는 다른 탐색.. 2023. 1. 30. 이전 1 다음
