[Swift] 섬 연결하기 프로그래머스 코딩테스트

방법을 찾지못해 검색중 크루스칼 알고리즘을 알게되었다.

아래 링크에 자세하고 쉽게 설명되어있다.

https://fomaios.tistory.com/entry/프로그래머스-섬-연결하기-Swift

해당 알고리즘을 모르면 아래 해설도 이해가 어려울것이다.

 

해결 방법

 

우선 크루스칼 알고리즘을 토대로

주어진 예시를 그림으로 그려보자면

이렇게 두개의 사이클을 만들어 버리게 된다.

이 두개의 사이클을 피해야 한다.

 

크루스칼 알고리즘 대로라면 우선 처리 순서를 연결 값이 낮은 순서

0-1

1-3

0-2

1-2 (여기서 사이클 현상이 나므로 제외)

2-3 (여기서 사이클 현상이 나므로 제외)

이 순서 대로 진행해야하고

 

사이클 현상 제외를 위해

0-1의 부모는 nil → 0 (0:[0,1])

1-3의 부모는 3은 부모가 없으나 1의 부모가 0 이므로 nil→0 (0:[0,1,3])

0-2의 부모는 2는 부모가 없으나 0의 부모가 0 이므로 nil→0 (0:[0,1,3,2])

1-2 의 부모는 둘다 이미 0로 같으므로 사이클로간주

2-3 의 부모 둘다 0이므로 사이클로 간주

이렇게 진행 되어야한다.

 

예제에 테스트가 하나밖에없어 여러 테스트를 가져왔다.

 

테스트예시

//solution(4, [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]])
//solution(5, [[0, 1, 5], [1, 2, 3], [2, 3, 3], [3, 1, 2], [3, 0, 4], [2, 4, 6], [4, 0, 7]])
//
//solution(5, [[0, 1, 1], [3, 4, 1], [1, 2, 2], [2, 3, 4]])
//solution(4, [[0, 1, 5], [1, 2, 3], [2, 3, 3], [1, 3, 2], [0, 3, 4]])
//solution(5, [[0, 1, 1], [3, 1, 1], [0, 2, 2], [0, 3, 2], [0, 4, 100]])
//solution(6, [[0, 1, 5], [0, 3, 2], [0, 4, 3], [1, 4, 1], [3, 4, 10], [1, 2, 2], [2, 5, 3], [4, 5, 4]])
//

 

 

 

 

 

var sortedCosts = costs.sorted { $0[2] < $1[2]}
var parentDict = [Int:Int]()
var costSum = 0

for i in 0..<sortedCosts.count{

}

우선 비용 배열을 가격순으로 정렬한다.

parentDict 에서는 값과 부모의 관계를 나타내는 데이터를 넣어줄것이고

costSum은 return할 값이다.

 

 

 

var num1 = 0
var num2 = 0
var thisCost = sortedCosts[i][2]

if(sortedCosts[i][0] < sortedCosts[i][1]){
    num1 = sortedCosts[i][0]
    num2 = sortedCosts[i][1]
}else{
    num1 = sortedCosts[i][1]
    num2 = sortedCosts[i][0]
}

var num1Parent = parentDict[num1]
var num2Parent = parentDict[num2]

반복문 안에서 첫번째 배열을 꺼낸다 ex> [0,1,1]

num1에는 두 값중 작은수 num2에는 큰수를 넣을것이다.

여기서는 num1=0 num2=1 가 들어갈것이다.

 

문제에서 주어진 값은 값이 오름차순으로 들어와있지만 ex>[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

혹시몰라 비교후에 값을 넣어줬다.

 

위에 언급한 parentDict에서 값과 부모간 관계를 다룬다했었다.

여기서에 num1과 num2의 부모를 가져와 num1Parent num2Parent를 불러온다.

만약 없다면 nil이 될것이다.

 

 

 

이제 부모들을 비교해 비용을 넣어주고 parentDict에 값을 넣어줘야한다.

이때 4개의 경우가 나온다.

 

if(num1Parent==nil && num2Parent==nil){
    parentDict[num1] = num1
    parentDict[num2] = num1
    costSum += thisCost
}else if(num1Parent == nil && num2Parent != nil){
    parentDict[num1] = num2Parent
    costSum += thisCost

}else if(num1Parent != nil && num2Parent == nil){
    parentDict[num2] = num1Parent
    costSum += thisCost

}else{

}

1. num1Parent num2Parent 둘다 nil인경우 → num1 num2 둘다 num1 을 부모로 가지고 비용을 증가시켜준다
2. num1Parent 만 nil 인경우 → num1 의 부모를 num2의 부모로 해주고 비용증가시켜준다
3. num2Parent 만 nil 인경우 → num2 의 부모를 num1의 부모로 해주고 비용증가시켜준다
4. 둘다 nil 아닌경우 → 여기도 두가지 경우가 나오므로 아래에 설명하겠다.

 

이제 4번의 경우는 두가지로 나뉜다

1. num1의 부모와 num2의 부모가 같은경우 → Cycle 발생한다 아무런 비용을 증가시키지 않는다.
2. 부모 다른경우 → num1부모 와 num2 부모를 비교후에 큰 부모를 가진 모든 값을 parentDict에서 작은 부모로 모두 변경해준 후에 비용을 증가시킨다.

}else{
  if(num1Parent == num2Parent){
      //cycle 제외
  }else{
     //부모다른경우 작은거로 다 대체
      if(num1Parent! <= num2Parent!){
          //큰 부모 가진 값들 다변경
          parentDict.keys.forEach { (key) in
              if(parentDict[key] == num2Parent){
                  parentDict[key] = num1Parent
              }
          }
      }else{
          parentDict.keys.forEach { (key) in
              if(parentDict[key] == num1Parent){
                  parentDict[key] = num2Parent
              }
          }
      }
      costSum += thisCost

  }
}

 

예로 현재 parentDict가 [1: 1, 0: 0, 3: 0, 2: 1, 4: 1] 인경우에서

두 값 0 과 4 가 만났다고 한다면

0의 부모는 0 , 4의부모는 1이다.

그럼 4의 부모는0으로 4뿐만 아니라 1,2 모두 부모를 0으로 바꾸어야한다.

 

 

 

전체 코드

func solution(_ n:Int, _ costs:[[Int]]) -> Int {
    
    var sortedCosts = costs.sorted { $0[2] < $1[2]}
    var parentDict = [Int:Int]()
    var costSum = 0

    for i in 0..<sortedCosts.count{
        var num1 = 0
        var num2 = 0
        var thisCost = sortedCosts[i][2]
        
        if(sortedCosts[i][0] < sortedCosts[i][1]){
            num1 = sortedCosts[i][0]
            num2 = sortedCosts[i][1]
        }else{
            num1 = sortedCosts[i][1]
            num2 = sortedCosts[i][0]
        }
        
        var num1Parent = parentDict[num1]
        var num2Parent = parentDict[num2]
        
        if(num1Parent==nil && num2Parent==nil){
            parentDict[num1] = num1
            parentDict[num2] = num1
            costSum += thisCost
        }else if(num1Parent == nil && num2Parent != nil){
            parentDict[num1] = num2Parent
            costSum += thisCost

        }else if(num1Parent != nil && num2Parent == nil){
            parentDict[num2] = num1Parent
            costSum += thisCost

        }else{
            if(num1Parent == num2Parent){
                //cycle 제외
            }else{

                if(num1Parent! <= num2Parent!){
                    parentDict.keys.forEach { (key) in
                        if(parentDict[key] == num2Parent){
                            parentDict[key] = num1Parent
                        }
                    }
                }else{
                    parentDict.keys.forEach { (key) in
                        if(parentDict[key] == num1Parent){
                            parentDict[key] = num2Parent
                        }
                    }
                }
                costSum += thisCost

            }
        }
        

    }
    
    
    
    return costSum
}