다익스트라5 [백준 11779] 최소비용 구하기 2 www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 알고리즘과 역추적을 하는 문제이다. eazymean.tistory.com/384 [알고리즘] 최단 경로 역추적 다익스트라 알고리즘과 플로이드 와샬을 사용한 최단거리 찾기 문제에서 종종 출제되는 경로 역추적 문제이다. 최단 거리와 그 경로를 찾는 문제로 다익스트라 알고리즘과 플로이드 와샬의 역 eazymean.tistory.com 다익스트라에서의 역추적은 비교적 단순하다.. 2021. 4. 11. [백준 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 다익스트라를 사용해서 노드 간의 거리를 구해준다. v1과 v2를 무조건 지나야 하므로 1 -> v1 -> v2 -> last 1 -> v2 -> v1 -> last 사이의 거리를 비교하여 작은 값을 리턴해준다. 양방향 그래프이고 비용이 같으므로 v1-> v2 == v2 -> v1이다. 따라서 사이 값을 mid로 한번만 구한다. 다익스트라 특성상 하나의 출발지로부터 모.. 2021. 1. 6. [백준 2665] 미로만들기 www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 최소거리기 때문에 bfs나 다익스트라 둘다 사용가능하다. 다익스트라를 연습하기 위해! 다익스트라로 풀었다. 검은색은 비용을 1 하얀색은 비용을 0으로 하여 arr[n-1][n-1]까지 도달하는 최소 비용을 계산한다. 처음 모든 거리는 inf로 초기화한후 조건을 만족하면 거리를 업데이트한다. 최소 비용을 구해야 하기 때문에 pop한 cur가 목적지에 해당한다고 break하지 않고 끝까지 진행한다. #include #in.. 2021. 1. 6. [백준 4485] 녹색 옷 입은 애가 젤다지? www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net bfs로 풀어도 되지만 다익스트라를 사용해서 풀었다. 다익스트라 사용시 우선순위 큐를 사용함. 다익스트라 구현방법 외우자..ㅠ #include #include #define INF 1e9 using namespace std; int n; int cave[125][125]; int dis[125][125]; struct s { int row, col, cost; }; struct cmp { bo.. 2021. 1. 5. 이전 1 2 다음