Dijkstra (5) 썸네일형 리스트형 (Python3) - LeetCode (Medium) : 2924. Find Champion II https://leetcode.com/problems/shortest-distance-after-road-addition-queries-idijkstra문제였습니다.📕 풀이방법📔 입력 및 초기화1. 인접리스트 형태로 map edges선언 후 key에는 node번호, value에는 현 node에 연결된 node들을 배열로 저장합니다. 2. 각 query별 최소거리 배열 distances 선언 후 빈 배열로 초기화합니다.📔 풀이과정n이 500이므로 O(n^3)의 시간복잡도로 가진 알고리즘은 사용할 수 없습니다. 단순 bfs나 플로이드 와샬을 사용한다면 시간초과가 뜹니다. 따라서 시간복잡도가 O((V+E)log(E))인 dijkstra를 사용해 해결합니다. 1. dijkstra를 구현합니다. 1-1.. (C++) - 백준(BOJ) 11779번 : 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net dijkstra 문제였습니다. 풀이방법 1. 입력 : 도시의 개수가 노드가 되며 버스의 경로가 간선이 됩니다. 이 생각을 적용해 인접리스트로 그래프를 만들어줍니다. 2. 다익스트라를 수행합니다. 인접한 간선들중 최소를 찾을 때마다 역추적을위해 배열에 저장합니다. 현재 정점을 cur, 다음 정점을 next라고 했을 때 prev[next] = cur로 저장한다면 nex.. (C++) - 백준(BOJ) 1753번 : 최단경로 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 다익스트라 문제였습니다. 풀이방법 dijkstra는 greedy, dp속성을 모두 가지고 있습니다. 시작정점 start -> x -> y -> z 로 가는 경로가 있을때 start에서 x로 가는 경로들 중 가장 작은 cost에 대해 갱신하는 방식입니다. Code #include #define INF 0x3f3f3f3f using namespace std; using pi.. (C++) - 백준(BOJ) 1504번 : 특정한 최단 경로 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 문제였습니다. 풀이방법 시작정점을 a, 거쳐야할 두 정점을 각각 v1,v2 도착정점을 b라고 가정했을때 가는 최단경로가 있다면 다음과 같이 두 가지 경로가 있습니다. 1) a -> v1 -> v2 -> b 2) a -> v2 -> v1 -> b 1), 2)중 최소인 경로를 출력, 경로가 없다면 -1을 출력해주면 됩니다. 1. 1)의 답은 a -> v1으로 .. (C++) - 백준(BOJ) 1238번 : 파티 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 문제였습니다. 풀이방법 i번 친구가 x마을로 가는데 걸리는 최소 시간과 x마을에서 i가 출발해 i마을에 도착하는데 걸리는 최소 시간의 합이 오고 가는데 거리는 총 소요시간이므로 다익스트라로 해당 값을 구해 최댓값을 출력해주면 됩니다. Code #include #define INF 0x3f3f3f3f using namespace std; using pii = pair; i.. 이전 1 다음
