Doby's Lab

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 답을 구하는 순서는 쉽게 알아낼 수 있었다. 1) 다익스트라를 통해 최단 경로 탐색 2) 해당 최단 경로를 없앰 3) 다시 한번 다익스트라를 통해 최단 경로를 구함 '해당 최단 경로를 없앰'을 해결하는 게 이번 문제의 핵심이다. 솔루션을 참고(https://jaimemin.tistory.com/617)하기도 했고, 바로 전에 풀었던 문제에서 '경로 역추적'이라는 키워..

https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 이번 문제에서 해결해야 하는 건 "최단 경로를 구했을 때 시작 노드에서 제일 처음 방문한 노드가 어디인가"를 어떻게 찾을지가 포인트였다. (참고 https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-1719-%ED%83%9D%EB%B0%B0) 참고한 포스팅에서 다음과 같이 정리할 수 있었다. 1) 다익스트라를 통해 각 노드로부터 최단 경로 구하기 2) 최단 거..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net [방법] s->g->h->x or s->h->g->x가 s->x로 가는 경로 중에 최단 경로여야 한다. 가중치 모두 양수이므로 다익스트라 알고리즘이 사용 가능하다. (경로를 구하는 방식은 이 문제를 통해 공부를 했었다. https://draw-code-boy.tistory.com/138) int path1_1 = fromS[g] + fromG[h] + fromH[x]; int path1_2 ..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 일반적인 다익스트라(우선순위 큐 사용)를 제출하면 시간 초과가 난다. 우선순위 큐에서 현재의 top이 도착하려는 노드(v2)가 되면 이미 최소 비용은 구했기 때문에 다른 노드를 향한 최소 비용을 구할 필요 없이 바로 종료시켜줬다. [AC 코드] #include #include #include #include #define MAX 1000 + 1 #define IN..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 두 개의 다익스트라 알고리즘을 선언하여 문제를 풀 수 있었다. 우선 문제를 두 개로 나누어 생각할 수 있다. 1) 갈 때 시간 2) 돌아올 때 시간 3) 두 값 합한 것 중 최댓값 도출 1) 갈 때 시간 갈 때의 시간은 여러 노드들로부터 다익스트라를 돌려봤다. 그리고 X까지 가는 데에 드는 비용들을 배열에 저장해두었다. for (int i = 1; i N >> M >..

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 (https://yabmoons.tistory.com/364) 이번 포스팅은 링크에 걸어둔 다익스트라 포스팅을 정리한 포스팅으로 자세한 설명은 링크에 되어있다. [다익스트라 개념 정리] 시작 노드 -> 도착 노드로 가는 최소 비용(가중치)을 구하는 알고리즘 1. 첫 노드 방문 체크 2. 방문한 노드와 연결되어 있는 노드들 거리 업데이트 3. 방문한 노드와 연결..