다익스트라

https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 📝문제 📝풀이 처음 풀어보는 유형의 문제다. 아이디어를 못 떠올려서 도움을 받았다.. 만약 1-3-2-5 이런식으로 연결 된다고 치면 각각 edge들에 대하여 가중치들은 4, 3, 9 원이다. 여기서 k=1, 회선 하나는 공짜로 준다고 했으니 제일 비싼 9원을 빼면 남은건 4, 3 인데 이들 중 제일 비싼 회선 값만 return 하므로 ans=4 이 답이다..

https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr [문제] [풀이] 특정 거리까지의 마을만 배달이 가능하기 때문에 모든 정점에 대해 거리의 합을 알아야 한다 하지만 출발지는 고정되어 있다. => 다익스트라 알고리즘 이용 각 정점에 대한 거리 배열을 Distance라고 하면 주어진 K 보다 낮은 값을 가진 마을의 개수를 카운트 하면 된다. import java.util.stream.*; ..

https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr [문제] [풀이] 처음에 두 가지 방법을 떠올렷다. 1. 플로이드 와샬 2. 다익스..

https://www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net [문제] [풀이] 1. 다익스트라를 돌려서 N번 노드까지의 최단거리를 구하고 , 경로를 구한다. 2. 구한 경로의 edge를 하나씩 빼면서 다익스트라를 경로의 수 만큼 다시 돌린다. 3. 늘어난 시간 중 가장 긴 거리와 1번에서 구한 최단거리의 차이를 반환하면 끝. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 문제 풀이 쉽게 풀 수 있을줄 알았다 .. 최단 경로 찾아서 없애주고 , 처음 구한 최단경로보다 높은 값 나올때까지 다익스트라 다시 쓰면 되는줄 ..하지만 실패하고 반례를 살펴보니 다른 조건이 추가되어야 했다. 예를들어 , 0에서 출발하여 2로 도착하는 예시에서 최단 경로가 될 수 있는 경우의 수는 2가지이다. (0->3->2 , 0->3->1->2) 만약 0->3-..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 풀이 풀이 방식은 이전 포스팅과 동일하다. https://katastrophe.tistory.com/19 [BOJ] 백준 [1753] 최단경로 JAVA https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1..

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 문제 풀이 nlogn 시간복잡도인 우선순위큐를 이용한 다익스트라 기본 풀이다. 간선의 가중치 낮은 순으로 우선순위큐에 들어가기때문에 n^2 방식인 최소비용탐색하는 시간이 들지 않기때문 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 ..

https://www.acmicpc.net/problem/16197 문제 풀이 이 문제에서 내가 집은 포인트는 3 가지이다. 1. 동전 위치를 나타내는 Point 객체와 두 동전을 담고 움직이는 횟수를 나타내는 Move 객체를 생성 2. 우선순위큐를 이용하여 횟수가 적은 순서대로 처리 3. isRange(x,y) 로 범위를 벗어나는 조건을 이용해서 둘 중 하나만 떨어지는 경우를 체크 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64..