[Swift] 프로그래머스 섬 연결하기

Problem

 

코딩테스트 연습 - 섬 연결하기

---

Solution

 

해당 문제는 Greedy 문제입니다.

 

그 중에서도 크루스칼 알고리즘으로 풀어야하는 문제입니다.

 

크루스칼 알고리즘이란?🤔

 

"컴퓨터 과학에서, 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 변의 개수를 {\displaystyle E}E, 꼭짓점의 개수를 {\displaystyle V}V라고 하면 이 알고리즘은 {\displaystyle {\color {Blue}O}(E\log V)}{\color {Blue}O}(E\log V)의 시간복잡도를 가진다."

 

위키백과에 이렇게 정의되어 있는데요..... 저는 이해하기가 힘들더라구요....😅

 

그래서 열심히 이해해보려고 하고 찾아본 결과.... 

 

"가장 값이 낮은 연결로 우선 정렬한 뒤 사이클 즉,반복이 생기는 구간은 제외시켜주면 되는 알고리즘입니다!"

 

라고 설명드릴수 있겠네요.

 

이렇게 말하면 어려우니 예제로 설명드릴게요!!

 

먼저 아래와 같은 연결들이 있다고 가정할게요.

 

 

 

 

 

 

그렇다면 가장 각 연결간 값이 낮은 순으로 정렬해보면

 

1. 3-4 5

 

2. 3-5 20

 

3. 4-5 21

 

4. 1-2 23

 

5. 2-5 46

 

6. 1-4 99

 

로 정렬할 수 있겠죠?

 

그러면 저 순서대로 하나씩 실제로 연결해서 가장 낮은 총합을 구해봅시다!😎

 

먼저 3-4를 연결해주시면 총합은 5가 되겠죠?

 

 

 

 

그 다음으로 낮은 3-5를 연결해주면 총합은 25가 되겠죠?

 

 

 

그 다음으로 낮은 4-5를 연결해주어야 하는데요...

 

여기서 잠깐 4-5를 연결하게 되면 아래와 같이 사이클을 형성하게 됩니다. 😯

 

 

 

위에서와 같이 사이클을 형성하는 연결은 제외시켜줍니다!

 

그 다음으로 낮은 1-2를 연결시켜주면 총합이 48이 되겠죠?

 

 

 

그 다음으로 낮은 2-5을 연결시켜주면 총합은 94가 되고 모든 숫자가 4 - 3 - 5 - 2 - 1 로 연결된걸 볼수 있습니다!!

 

 

 

맨 마지막인 1 - 4는 4- 3 - 5 - 2 - 1의 사이클을 형성하므로 제외시켜주고 넘어가주면 가장 낮은 총합은 94가 됩니다.

 

 

 

크루스컬 알고리즘이 조금은 이해가 되셨나요?

---

728x90

그렇다면 이것을 어떻게 사이클을 형성하는지 알까요?🧐

 

바로 부모를 각 숫자마다 정해주는겁니다. (갑자기 부모가 나와서 당황스러우실텐데요.) 😟

 

만약 부모가 없다면 연결하는 숫자 중 더 낮은 숫자(왼쪽값)를 두 숫자의 부모로 지정합니다.

 

그리고 각 숫자의 부모가 같다면 그것은 사이클이 된다고 가정합니다.

 

또한 모두 부모가 있다면 왼쪽값의 부모로 오른쪽 값의 부모와 그 자식들의 부모를 바꿔줍니다.

---

이렇게 말하면 어려우니 예제로 설명드릴게요!!

 

 3-4가 연결되었을때 3의 부모와 4의 부모가 모두 없는 상태입니다.

 

그렇다면 숫자 중 왼쪽인 3이 3과 4의 부모가 됩니다. 

 

그러면 3의 부모는 3이 되고 4의 부모는 3이 되겠죠? (부모는 주황색 네모 박스로 표시해두겠습니다.)

 

 

 

그 다음으로 3 - 5를 연결하면 연결되는 왼쪽값으로 그 부모를 따라가게 됩니다.

 

 

 

 

1 - 2의 연결은 3 - 4의 연결과 같이 왼쪽 숫자가 부모가 되겠죠?

 

 

여기서 문제가 되었던 사이클이 발생하는 4 - 5의 연결입니다.

 

하지만 이미 4와 5는 부모가 있죠? 부모를 확인해보니 모두 3이네요.

 

고로 연결하려는 두 쪽의 부모가 같게 되어 사이클이라고 간주하게 되는거죠!!

 

 

마저 설명드리면 1 - 2의 연결은 3 - 4와의 연결처럼 왼쪽값이 부모가 됩니다.

 

 

 

 

여기서 만약 2 - 5를 연결하게 되면 어떻게 될까요?

 

2의 부모가 있는 상태이고 5의 부모가 있는 상태입니다.

 

이렇게 모두 부모가 있는 상태도 마찬가지로 왼쪽의 부모로 따라가게 되고 5와 연결된 모든 숫자의 부모 또한 동일하게 바뀌게 됩니다.

 

 

마지막으로 1 - 4를 연결하려고 하면 1의 부모는 1이고 4의 부모는 1이므로 같은 부모가 됩니다.

 

이는 곧 사이클을 형성한다는 뜻이므로 제외해주도록 합니다.

 

 

 

이렇게 크루스컬 알고리즘을 알아보았는데요.

 

코드로 작성하는 부분은 소스 코드를 참조해주세요!!

---

Source Code

 

 

 

 

---

P.S

 

처음엔 크루스컬 알고리즘이라는 것을 몰라서 그냥 완전탐색과 재귀로 각 숫자마다 연결의 모두를 탐색하고 

 

가장 낮은 값을 반환하면 되지않을까? 라고 코드를 짰더니 효율도 굉장히 안좋고 거의 대부분이 실패라고 나왔다....

 

뭔가 검색하지않고 내 생각으로 풀어야겠다고 다짐하고 풀었더니 거의 하루를 잡아먹었다....

 

다음부터는 정해진 시간만큼만 고민하고 모르겠으면 바로 검색해서 학습하도록 하는 것이 좋겠다.....

import Foundation

var costsCopy = [[Int]]()
var nCopy = Int()
var min = 10000000

func solution(_ n:Int, _ costs:[[Int]]) -> Int {
    let numbers = (0..<n).map{$0}
    costsCopy = costs
    nCopy = n
    
    numbers.forEach{
        greedy($0, cost: 0,numbers: Set<Int>(),history: [String]())
    }

    return min
}

func greedy(_ start:Int,cost:Int,numbers:Set<Int>,history:[String]){
    
    if cost >= min {
        return
    }
    
    var currentNumbers = Set(numbers)
    
    currentNumbers.insert(start)
    
    if currentNumbers.count == nCopy {
        print(history,cost)
        min = cost
        return
    }
    
    let startFilter = costsCopy.filter{$0[0] == start || $0[1] == start}
    
    for s in startFilter {
        
        var destination = Int()
        
        if s[0] == start {
            destination = s[1]
        }else {
            destination = s[0]
        }
        var newHistory = history
        let h = "\(start)\(destination)"
        if  history.contains(h) {
            return
        }
        newHistory.append(h)
        
        let currentCost = cost + s[2]
        
        greedy(destination, cost: currentCost,numbers: currentNumbers,history: newHistory)
        
    }
}

solution(4, [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]])

---

Reference

 

아래 블로그의 풀이가 많은 도움이 되었습니다.

 

섬 연결하기 (프로그래머스)