YJLee-devlog 🍎

1. 문제 그래프 내의 모든 정점을 잇는 스패닝 트리 중 그 가중치의 합이 최소가 되는 트리가 최소 신장(스패닝) 트리 위 최소 신장 트리를 구하는 대표적인 알고리즘인 크루스칼 알고리즘을 구현 2. 문제 설계 최소 신장 트리를 구하는 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 두 정점을 이어나가면서, 트리는 사이클이 없는 그래프이기 때문에 사이클이 없어야 함 그렇기 때문에, 간선의 가중치를 기준으로 그래프를 오름차순 정렬하고 사이클이 발생할 수 있는지 여부를 파악해야 함 사이클이 발생하려면, 같은 트리내의 정점을 이을 경우 사이클이 발생하므로, 현재 두 정점이 같은 트리내에 속하는지 여부를 검사해야 하며, 같은 트리내에 없을 시 같은 트리로 묶어주는 작업이 필요함 위 두가지 작업을 위해서 Disjo..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 문제에서 양방향 도로가 아님에 주의하라는 점을 고려하여, 단방향 그래프를 구성하고 그 그래프에 대한 역방향 그래프를 구성한 후 철수네 집에 대하여 두 그래프에 대해 다익스트라 알고리즘을 적용하게 되면, 모든 마을 사람들이 철수네 집에 오고 가는 최단 경로를 모두 구할 수 있음 따라서 두 그래프에 대한 다익스트라 알고리즘을 적용한 후, 두 최단 거리 배열의 모든 원소의 합을 더해줌으로써 문제를 해결할 수 있음 5. 전체 코드 //MARK: - 파티 //MARK: - Framework import Foundation //MARK: - Type struct Graph { //MARK: - Property var edges, costs: [Int] //M..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 가중치가 있는 그래프에서 최단 거리를 구하기 위해 다익스트라 알고리즘을 적용할 수 있는데, 위 문제의 경우는 특이하게 시작점부터 시작해서 특정 두 정점을 무조건 거쳐서 도착지점까지의 최단 거리를 구해야 함 따라서 꼭 거쳐야 하는 두 정점을 A, B로 가정하면, 시작점 -> A -> B -> 도착점, 시작점 -> B -> A -> 도착점 두 가지의 경우를 모두 고려해보고, 그 중 최단 거리를 구함으로써 문제를 해결할 수 있고, 다익스트라 알고리즘을 총 6번 적용해야함을 알 수 있음 5. 전체 코드 //MARK: - 특정 최단거리 //MARK: - Framework import Foundation //MARK: - Type struct Graph { ..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 그래프의 간선의 가중치가 없기 때문에 BFS로 최단 거리를 구해도 되지만, 다익스트라를 이용해서 해당 문제를 해결할 수 있음 각 간선의 가중치를 1로 가정하고, 다익스트라 알고리즘을 적용하여 시작점부터 도착점까지의 최단 거리를 구함으로써 문제를 해결함 5. 전체 코드 //MARK: - 최단거리 //MARK: - Framework import Foundation //MARK: - Type struct Graph { //MARK: - Property var edges: [Int] var costs: [Int] //MARK: - Initializer init() { self.edges = [] self.costs = [] } } //MARK: - Var..

1. 문제 간선의 가중치가 존재하는 그래프의 최단 경로를 찾는 다익스트라 알고리즘을 구현 2. 문제 설계 처음 각 노드에 대한 최단 경로를 큰 값으로 초기화 하고, 시작점의 최단 경로 값을 0으로 시작하고, 방문 처리를 한 후 시작점으로부터의 최단 경로 값과 인접한 정점들의 최단 경로의 합 중 더 작은 값으로 저장 이후 다시 아직 방문하지 않은 정점에 대한 최단 경로 값의 최소값을 찾고 방문 처리를 함 위 과정을 모든 정점에 대해 반복하게 되면 시작점으로부터 모든 정점에 대한 최단 경로를 구할 수 있음 3. 전체 코드 //MARK: - 다익스트라 알고리즘 //MARK: - Framework import Foundation //MARK: - Type struct Graph { //MARK: - Proper..