최단경로알고리즘3 [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. [G4] 백준 11404 - 플로이드 (Python3) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해결방법 플로이드-워셜 알고리즘을 이용해 풀이했다. 풀이👀 이번 입력은 [출발-도착-비용]이 들어오는데, 출발과 도착 정보가 동일한 입력도 포함된다. 그래서 이런 경우를 대비해주어야 한다. 이 문제는 모든 경로로 이동하는 최소비용 정보를 (출력하라고)요구하고 있다. 그러므로 출발과 도착 정보가 동일하게 주어질 땐 기존 입력값과 비교해서 더 작은 값을 반영해서 이 문제를 풀면 된다. 코드🐱👓 IN.. 2023. 1. 31. [22동계모각코] 8회 계획 및 평가 시작 시간 : 23-01-31 오후 6시 오늘의 목표 플로이드-워셜 알고리즘 공부 플로이드 워셜 알고리즘이란? 모든 노드에서 다른 모든 노드까지 이동하는 최소비용을 구하는 알고리즘이다. 기본 동작은 다익스트라 알고리즘과 비슷하다고 느꼈다. A에서 B까지 이동하는 것보다 A와 B 사이에 k를 지나 도달하는 게 더 저렴한 비용으로 도달할 수 있다는 점에서 이 알고리즘이 만들어진 듯했다. 이 알고리즘은 정해진 점화식에 따라 비용이 수정된다는 점에서 다이나믹 프로그래밍에도 속한다고 한다. D_ab = min(D_ab, D_ak + D_kb) D_ab : a에서 b로 가는 거리(distance) 시간복잡도🕐 입력 노드가 N개 일때, 모든 노드에 대해서 다른 모든 노드(N개)로 가는 경로를 탐색한다. 그렇기 때문에.. 2023. 1. 31. 이전 1 다음
