다익스트라 (4) 썸네일형 리스트형 [백준/Swift] 11779: 최소비용 구하기 PS일지 문제 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 간단한 문제 요약 다익스트라 최단 경로 문제입니다! A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시켜야합니다. 이때 A->B까지 갈 때 최소로 드는 비용과 경로를 출력해야한다. 출 -> 도착 지점은 항상 지정되어있다. 고려해야 할 사항 문제를 구현하면서 답은 여러 개가 정답일 수 있습니다. 문제 풀이, 했갈렸던 점 PS 일지 문제를 풀면서 신기했던 점이 있습니다. 예제 입력에 대한 예제 출력의 도시 경로 출.. [백준/Swift] 1504: 특정한 최단 경로 문제 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 간단한 문제 요약 방향성 없는 그래프가 주어진다. 1->N 정점으로 최단 거리로 이동하려고 한다. 이때 문제에서 주어진 임의의 두가지 정점은 반드시 통과해야 한다. 물론 한번 이동했던 정점, 간선을 다시 이동할 수 있다.(최단 경로로 이동한다는 전제하에) 1 -> N까지 최단 경로를 갈 때 반드시 임의의 두 정점 v1, v2를 거쳐 최단 경로를 가는 경로 길이를 출력 해야한다. 고려해야 할 사항 v1 -> v2로.. [백준/Swift] 4482 : 녹색 옷 입은 애가 젤다지? 문제 (링크) 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 간단한 문제 요약 '도둑루피' 라는 검정색 루피를 획득하면 소지한 루피가 감소한다. N*N의 동굴에는 도둑 루피로 가득하다. 젤다는 [0][0]위치에 있고 출구는 맨 아래칸 [N-1][N-1]로 이동해야한다. 동굴의 각 칸은 도둑 루피가 있다. 잃는 금액을 최소로 해서 동굴의 출구로 이동해야 한다. 한번에 한 칸 이동할 수 있다. 고려해야 할 사항 도둑 루피 크기가 K인 특정 칸을 지나면 K루피를 잃는 다는 뜻 시작점 [0][0].. [알고리즘]다익스트라 최단 경로 알고리즘 개념 부수기 / heap이 뭐야? 다익스트라 최단 경로 알고리즘 정점 한개를 기준으로(=시작 정점) 다른 모든 정점을 도착하는 단일점에서의 최단 경로 알고리즘 방향 그래프, 무방향 그래프 모두 적용 간선의 가중치가 음수면 다익스트라 알고리즘을 사용할 수 없다. 가장 가까운 정점(방문x 정점)을 선택해 추가할 때, 추가된 새로운 정점에 의해 단축되는 경로가 있다면 해당 경로로 최단 경로를 수정하는 알고리즘이다. 집합 또는 vertex방문체크를 하면서 최단 경로를 구할 경우( 원래의 알고리즘 ) 시간복잡도는 O(E + V^2) == O(V^2)이다. 우선순위 큐를 활용할 경우 시간 복잡도는 O(ElogV)이다. Algorithm 1. set distance 2.시작 정점 방문 체크 3. 방문하지 않은 정점 중 시작점과 최소거리인 정점을 찾아.. 이전 1 다음
