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..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 위 문제는 이전 미로 찾기 문제를 응용한 문제로, 시작점에서 각 벽까지의 최단거리, 도착지점에서 각 벽까지의 최단거리를 각각 배열에 저장하고, 두 배열에 대해 벽에 해당되는 값의 합의 최소값을 찾음으로써 문제를 해결할 수 있음 주의할 점은, 각각의 최단거리를 찾기 위해 BFS를 진행할 때, 미로의 범위를 벗어나지 않고 방문 여부를 검사하면서 탐색하되, 벽에 해당되는 부분은 방문하면 안됨 위 과정을 통해 각각의 최단거리를 구하고, 두 배열의 합의 최소값을 찾기 위해 완전탐색을 하게 되는데, 이 때 특정 벽까지의 최단거리 값이 0일 수 있으므로 이에 대한 예외처리가 필요함 따라서 O(N * M)의 시간복잡도로 문제를 해결할 수 있음 5. 전체 코드 /..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 위 문제도 * 2 연산, / 3 연산 결과를 각각 노드라고 가정하면 BFS를 적용하여 문제를 해결할 수 있음 K는 1이상 값이므로 / 3 연산 시 0이 나올 수 있기 때문에 0번 위치는 이미 방문했다고 처리를 해야 함 * 2 연산 시 마을의 개수를 넘어가면 안되기 때문에 해당 예외처리도 필요함 위 조건을 만족하면서 인접한 노드를 방문할 때마다 count 값을 증가시켜 주고, 해당 count 값이 K번 마을부터 전염병이 퍼진 마을의 개수이므로 전체 마을의 수(N) - count를 통해 전염병이 퍼진 마을을 제외시켜 줌으로써 전염병이 퍼지지 않은 마을의 수를 구할 수 있음 5. 전체 코드 //MARK: - 전염병 //MARK: - Framework i..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 위 문제는 개인적으로 너비우선탐색을 사용해야겠다고 떠올리는게 힘들었던 문제 단순히 * 2 연산과 / 3 연산을 반복해서 진행하다보면 시간초과가 발생할 수 있음 또, * 2 연산 시 5자리 이상 넘어가는 것을 방지해주어야 함 위 조건을 만족하면서 현재 값에서 * 2 한 위치, / 3 한 위치를 각각의 노드로 보고 해당 위치에 대해 BFS를 진행하게 되면 미로 찾기 문제에서 거리를 저장하듯이 이전 버튼 횟수 + 1을 각각의 위치에 누적하고, 최종적으로 원하는 값의 위치의 버튼 횟수를 출력함으로써 문제를 해결할 수 있음 BFS로 탐색하기 때문에 해당 위치(연산 결과)를 최초에 발견했을 때 누적 값이 최솟값임이 보장되고, 방문 여부를 검사하므로 두번 이상..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 그림 1 처럼 입력으로 주어지는 2차원 배열을 그래프라고 가정하고, 현재 원소가 1이라면 상, 하, 좌, 우 방향으로 그래프 탐색(DFS or BFS)을 진행하고, 더이상 상, 하, 좌, 우에 인접한 원소 1이 없다면 탐색을 멈추고 그 때의 count 값을 별도의 배열 혹은 리스트에 저장 이 문제의 경우, 2차원 배열의 입력에 주의해야 하는데, 한 줄 단위로 입력을 받고 있기 때문에, 문자열에 각각의 원소를 정수로 변환하여 배열을 구성해야 함 마지막으로, count 값을 담은 리스트를 정렬하고, 리스트의 크기와 원소를 차례로 출력함으로써 문제를 해결할 수 있음 5. 전체 코드 //MARK: - 단지 번호 붙이기 - BFS //MARK: - Fram..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 가중치가 없는 그래프에서 최단 거리를 찾기 위해서는 그래프 탐색 알고리즘 중 BFS 알고리즘이 적절함 DFS도 최단거리를 찾을 수는 있지만, 깊이우선탐색은 계속 해서 낮은 레벨로 탐색하므로 적절하지 않음 인접한 노드들부터 차례로 방문하는 너비우선탐색으로 방문할 때마다 거리를 이전 노드의 거리에 + 1 씩 누적시키고, 마지막으로 목적지의 거리를 출력함으로써 문제를 해결할 수 있음 5. 전체 코드 //MARK: - 미로 찾기 //MARK: - Framework import Foundation //MARK: - Type struct Node { //MARK: - Property var x, y: Int //MARK: - Initializer init(_..