본문 바로가기
728x90

알고리즘/다익스트라

 (4)
[KOTLIN] 배달 - 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 문제 설명 N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에..
[백준][KOTLIN] 13308 주유소 - https://www.acmicpc.net/problem/13308 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 풀이 1. 각 도로의 거리가 가중치가 있다 : 다익스트라 알고리즘 이용 2. 각 도시의 주유비가 다르다 : 각 도시까지 주유비에 따른 최소 비용을 저장하는 동적 프로그래밍(dp[i][j] : i 도시까지 j 주유비로 가는 최소 비용) 코드 import java.io.* import java.util.* fun main(args: Array) { val br = Buff..
[알고리즘][KOTLIN] 다익스트라(w. 우선순위큐, 인접 리스트) [알고리즘][KOTLIN] 다익스트라 정의 최단 경로를 찾는 그래프(DFS, BFS)알고리즘에서 각 경로에 가중치가 있어 최소 가중치의 경로를 찾는 알고리즘 그래프 알고리즘으로 경로를 탐색하고 최소 경로를 저장하기 위해 DP를 활용 jefflim-81.tistory.com 위의 알고리즘을 풀 때 노드 및 간선의 입력이 커지게 되면 기본 다익스트라 알고리즘의 경우 O(n^2) 시간 복잡도를 가지므로 인접 리스트를 이용하여 시간복잡도를 해결해야하는 상황이 발생할 수 있다. 코드 import java.io.* import java.util.* fun main(args: Array) { val br = BufferedReader(InputStreamReader(System.`in`)) // V : 노드의 개수 ..
[알고리즘][KOTLIN] 다익스트라 정의 최단 경로를 찾는 그래프(DFS, BFS)알고리즘에서 각 경로에 가중치가 있어 최소 가중치의 경로를 찾는 알고리즘 그래프 알고리즘으로 경로를 탐색하고 최소 경로를 저장하기 위해 DP를 활용한다. 백준 알고리즘 연관 문제 1162, 1238, 1753, 1916 문제 아래 주어진 각 노드와 연결된 경로에서 시작 시점인 노드1에서 각 노드까지의 최단 거리를 구한다. 연결된 경로와 경로의 가중치를 저장하는 maps 배열을 선언한다.(크기 : n + 1, n은 노드의 개수) DP 를 이용하여 최단 거리를 저장하기 위한 distance 배열을 선언한다.(크기 : n + 1, n은 노드의 개수) 이때 distance 배열의 각 항목은 Int.MAX_VALUE 로 초기화 한다. 최소 거리를 비교하기 위해... ..

티스토리툴바