YJLee-devlog 🍎

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 SCC 문제를 응용한 문제로, 코사라주 알고리즘에서 역방향 그래프에 대해서 DFS를 한번 더 적용하는 것과 다르게 생각해야 함 결론적으로, SCC인 그래프들은 어떠한 정점을 터뜨려도 다 터지기 때문에 1개의 정점으로 봐도 무방함 따라서 SCC인 그래프들을 1개의 정점으로 보고, 나머지에 대해 가장 효율적이게 폭발물을 설치해야 하는데, 자세히 살펴보면 나에게 들어오는 간선이 없는 정점에 대해 터뜨리게 되면 가장 최소한의 다이너마이트를 사용하여 폭발물을 설치할 수 있음 이를 코사라주 알고리즘을 응용하여 빠져나오는 순서를 기록하고, 재귀함수(DFS)의 특성상 가장 나중에 빠져나온 정점이 나에게 들어오는 간선이 없는 간선이므로, 이번에는 역방향이 아닌 원..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 방향 그래프에서 같은 그룹의 정점이라면 서로 오고갈수 있는 경로가 존재하는 그룹끼리 그래프를 나누는 것을 SCC(Strongly Connected Component)라고 하며, 이를 구할 수 있는 대표적인 알고리즘이 코사라주 알고리즘 따라서 주어진 그래프를 정방향 그래프와 역방향 그래프 두가지로 구성하고, 정방향 그래프에 대해 DFS를 적용하여 빠져나오는 순서대로 그 정점의 번호를 기록하고, 가장 나중에 빠져나온 정점이 역방향 그래프에서는 단말노드가 되므로, 역방향 그래프에 대해 가장 나중에 빠져나온 정점부터 다시 DFS를 적용하게 되면 SCC를 구할 수 있음 따라서 O(V + E)의 시간복잡도로 문제를 해결할 수 있음 5. 전체 코드 //MARK..

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로 탐색하기 때문에 해당 위치(연산 결과)를 최초에 발견했을 때 누적 값이 최솟값임이 보장되고, 방문 여부를 검사하므로 두번 이상..