다익스트라
-
백준 1238 파티Algorithm/BOJ 2021. 4. 19. 14:00
출처: www.acmicpc.net/problem/1238 분류: 최단거리, 다익스트라 접근방식 단방향 그래프에서 목적지 X까지 갔다가 돌아오는 비용이 최대인 경우를 찾는 문제였습니다. 즉, (출발지 -> X)의 최단거리 + (X -> 출발지)의 최단거리를 구하는 게 목표였습니다. 저는 다익스트라 알고리즘으로 각 경우의 최단거리를 구해서 해결해줬습니다. 해결방법 import Foundation typealias Edge = (dest: Int, dist: Int) let nmx = readLine()!.split(separator: " ").map { Int(String($0))! } let (n, m, x) = (nmx[0], nmx[1], nmx[2]) var map = [[Edge]](repeati..
-
백준 1916 최소비용 구하기Algorithm/BOJ 2021. 4. 6. 22:11
출처: www.acmicpc.net/problem/1916 분류: 다익스트라 접근방식 전형적인 최단경로 문제였습니다. 다익스트라 알고리즘으로 해결할 수 있었습니다. 다익스트라 알고리즘을 알면 별도의 설명은 필요 없을듯 하네요. 다익스트라 포스팅을 한 번 해야겠습니다.. 해결방법 let n = Int(readLine()!)! var cities = [[(end: Int, value: Int)]](repeating: [], count: n+1) for _ in 0..