Algorithm/Dijkstra (13) 썸네일형 리스트형 (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) 14938 : 서강그라운드 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net dijkstram로 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 지역 개수 n, 수색 범위 m, i번 지역까지의 거리를 저장할 일차원 배열 dist, item정보를 입력받을 일차원 배열 items, 답을 출력할 ans, graph정보를 입력할 vector형 변수 graph를 선언해줍니다. 이후 적절히 입력해줍니다. 📔 풀이과정 시작점으로부터 최단거리로 어떤 지역으로 갔을 때 m이하의 거리라면 .. (C++) - 백준(BOJ) 18223번 : 민준이와 마산 그리고 건우 https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net dijkstra문제였습니다. 📕 풀이방법 📔 입력 및 초기화 인접그래프를 만들어줍니다. 📔 풀이과정 1 ~ p까지의 최단거리 + p ~ v까지의 최단거리 cost + nextCost){ dist[next] = cost + nextCost; pq.push({dist[next],next}); } } } return dist[endPoint]; } i.. (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) 21738번 : 얼음깨기 펭귄 https://www.acmicpc.net/problem/21738 21738번: 얼음깨기 펭귄 첫째 줄에 얼음 블록의 개수 $N$($ 3 \leq N \leq 328\,000$)과 지지대의 역할을 하게 되는 얼음의 개수 $S$($ 2 \leq S \leq N-1$), 펭귄이 위치한 얼음 블록의 번호 $P$($ S \lt P \leq N$)가 주어진다. 지지대의 역 www.acmicpc.net dijkstra로 해결한 문제였습니다. 풀이방법 1. 간선을 인접리스트 형태로 저장합니다. 2. 펭귄 위치에서 i번째 얼음 볼록으로 가는 최단거리를 모두 저장합니다. 거리가 모두 1이기 때문에 이것이 곧 깰 수 있는 얼음의 개수가 됩니다. 즉, i번 얼음 블록을 깬다면 연쇄적으로 펭귄과의 최단거리만큼의 얼음이 깨진.. (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 2 다음
