알고리즘 문제 통행료 문제 https://github.com/Hline/algorithm/blob/master/SW210813_%ED%86%A8%EB%B9%84/%ED%86%A8%EB%B9%84.txt 샘플케이스 https://github.com/Hline/algorithm/blob/master/SW210813_%ED%86%A8%EB%B9%84/in 알고리즘 2021.12.01
알고리즘 문제 Main Road 풀이 1. 시작점과 출발점을 찾아야함 1.1. 임의의 끝점에서 다익스트라로 가장 먼 점 탐색 1.1. 가장 먼 점에서 다익스트라로 다시 가장 먼 점 탐색 1. 시작점과 출발점 경로 내의 마트 탐색 1.1. Main Road 내의 마트임을 표시 1. UnionFind를 변형하여 각 점별로 Main Road까지의 거리 계산 알고리즘 2021.08.06
백준 1854 K번째 최단경로 BOJ 1854 K번째 최단경로 풀이: 1. 도로가 단방향. 2. 시작점은 경로비용 0 (문제에서 제시) 3. 시작점은 1번도시로 고정 이 전제하에 각 도시에 대해 모든 최단경로를 가장 작은 순으로 정렬했을 때 문제에서 주어지는 K번째 경로비용을 구하면 된다. 다만 모든 최단 경로를 구할 경우 메모리 초과가 발생한다. 따라서 모든 경로를 탐색하면서 각 K번째 최단경로까지만 보관한다. 각 경로의 최단경로를 보관하기 위해 입력받는 순간 정렬되는 Priorityque를 배열로 사용한다. (PriorityQueue[] costList = new PriorityQueue[N]; //도시 개수만큼 생성) que에 들어가는 순간 정렬되는 효과를 이용한다. 적은 비용은 두고 큰 비용은 그거보다 작은 비용을 만날 경우 .. 알고리즘 2021.06.02
백준 1238 파티 Java BOJ 1238 파티 Java 풀이: 각 마을 -> 파티 목적지 에 드는 비용 + 파티 목적지 -> 각 마을 에 드는 비용 시작점을 파티 목적지로 설정하고 시작점에서부터 최소비용을 구하면 각 마을까지의 비용을 구할 수 있다. 하기 이미지의 파란색 글씨 중 1: 각 마을 -> 파티 목적지 2: 파티목적지 -> 각 마을 3: 1번마을->파티목적지까지의 연산. que.add(Node(To, Value)), 비용 Dist[], 방문여부 Visited[] 1번 마을 비용을 메인 Dist에 등록 4: 3번 마을-> 파티목적지까지의 연산. 5: 4번 마을-> 6: 파티목적지(2) -> 각 마을 알고리즘 2021.05.22
