최근 크리스토피데스 알고리즘을 직접 구현해서 사용해볼 기회가 생겼다. Swift 뿐만 아니라 다른 언어에서도 이 알고리즘을 순수하게 작성한 자료가 없는 것 같아서 따로 글로써 작성해본다.(*순수하게라는 뜻은 내장 라이브러리를 사용하지 않고 구현한 것을 뜻한다) 다만, 내가 구현한 알고리즘은 TSP문제에서 시작 정점이 정해져있고 다시 시작 정점으로 돌아오지 않는 경우에 적용할 수 있는 알고리즘이다. 만약 기존 TSP 문제의 상황에서 사용하고자 한다면 몇가지 수정을 거쳐야한다. 이 점 참고하면 좋을 듯 하다. 크리스토피데스 알고리즘이란?TSP(외판원 순회 문제)는 한 세일즈 맨이 자신의 도시에서부터 시작하여 다른 도시들을 방문해가며 출장을 다녀야할 때, 소모해야하는 최소 비용을 구하는 문제이다. 유명한 N..
https://www.acmicpc.net/problem/21940 알고리즘 분류: 플로이드 와샬 (모든 정점에서 다른 모든 정점 까지의 최단 경로) 풀이: 1. 플로이드 와샬 -> 모든 간선의 최소 길이를 구함 2. 각각의 노드에서 도시마다 왕복시간을 구함 3. 구한 왕복 시간의 최대가 최소가 되는 도시들을 선정. 코드: import Foundation let input = readLine()!.split(separator: " ").map{ Int($0)! } let (N, M) = (input[0], input[1]) var p = Array(repeating: Array(repeating: Int.max, count: N+1), count: N+1) for _ in 0..= timeSum { if..