[프로그래머스] (Swift) 섬 연결하기 (lv.3, 그리디, 크루스칼 알고리즘)

🟠 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

 

🟠 나의 풀이

아니,, 전혀 생각해내지 못했다. 처음에는 bfs로 돌려서 방문 체크를 하면서 최소 비용을 찾아내고 싶었다. 근데 생각하다가 막힌게,,, "사이클 만들어지는 것은 어떻게 판단하지?"였다. 단순히 1,2,3 만 연결되어있다면 세개가 연결된 경우를 찾아낼 수 있다. 2차원 배열을 이용해서 [1,2] [2,3] [1.3] 머 이런식으로 확인해볼 수도 있겠지,, 근데 이게 만약 8개 그 이상이 사이클을 돌게 되면? 1-2-3-4-5-6-7-8 이렇게 연결되어있는데, 문제에 의하면 1과 8은 연결되어있는 것으로 간주한다. 이런경우,,, 어떻게  저 2차원 배열에서 찾을 수 있는가??? 없다!!!!!!!!!! 아오,, 복잡해 그래서 결국 인터넷 찬스를 썼다...

가끔,, 내 블로그에 와서 안부도 남겨주셨고, 나도 자주 방문하는 formagran님의 블로그에 정말 끝내주게 설명이 되어있었다. 진짜 글 한번읽고 이해 완료 ㅋㅋㅋㅋㅋ

https://fomaios.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0-Swift

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

 

이 글을 참고해서 풀이를 생각해보길,, 아니 그냥 저기 나와있는 크루스칼 알고리즘 그 자체가, 이 문제의 답이기도 하다!

처음들어봤는데, ,, 아주 간단하게 말해보자면

 

🔖 크루스칼 알고리즘

최소 비용을 가진 그래프 노선들을 위주로 더해나가다가 순환 사이클 (반복) 이 발생하면 그 노선은 비용에서 제외해주는 알고리즘이다. 여기서 순환이란, 아래 그림에서 노란색 선으로 연결되었을때, 그래프가 사이클을 형성하는 경우를 의미한다.

이 경우를 그럼 어떻게 판단해줄까? 여기 알고리즈에서는 부모를 생성해주는 방식을 사용한다. 그림으로 간단하게 그려보겠다.

위 그림을 보면, 빨간글씨로 숫자가 써있다. 그게 바로 여기서 생성한 부모이다. 주황색 선을 연결했을 경우, 1과 3중에 더 작은수 (왼쪽에 있는수)를 부모로 삼는다. 그럼 노드1의 부모는 1, 노드3의 부모도 1이 된다. 
연두색 선을 보자. 처음에 노드4와 노드5가 연결됐다고 치자. 그럼 더 왼쪽에 있는 수, 4가 부모가 된다. 그럼, 노드4와 노드5의 부모는 전부 4가 된다.
이제 노드5와 노드6을 연결해보자. 노드5와 노드6중에 노드5가 더 왼쪽에 있다. 노드5의 부모를 함께 공유해서 노드6에게도 4를 부여한다. 이런식으로, 더 왼쪽에 있는 노드의 부모 번호를 가져나가도록 설계해줘야한다.

그럼 이제 보라색이 연결된다면?

보라색이 연결된 것을 보면, 연결된 두 노드의 부모는 전부 4이다. 이렇게 마주치는 두 노드의 부모번호가 같다면, 결국 사이클을 생성한다는 의미가 된다! 그러므로, 보라색 부분은 연결에서 제외시킨다.

이런식으로 순환을 찾아나가고, 순환이 만들어지는 순간! 비용 추가에서 제외시켜나가면 된다!!  생각보다 너무너무 간단하다.

그럼!! 어떤 순서대로 연결하냐고??  저 연두색, 주황색, 보라색 형광펜은 그냥 임의로 막 연결지은 것인데, 크루스칼 알고리즘에서는 비용이 가장 적은!! 순서대로 연결한다. 그래야 최소비용이 나오니까! 이것을 그대로 코드로 구현하면, 바로 섬 연결하기의 정답이 된다.

🟠 정답코드

import Foundation

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

    for cost in sortedCosts {
        if !isCycle(parentArr: parentIdx, left: cost[0], right: cost[1]) {
            // 사이클 형성 안되면, 부모 바꿔주고
            // 작은 node 번호를 가진 애의 부모 번호를 갖게 된다.
            var newParent = 0
            var oldParent = 0

            if cost[0] > cost[1] {
                newParent = parentIdx[cost[1]]
                oldParent = parentIdx[cost[0]]
            } else {
                newParent = parentIdx[cost[0]]
                oldParent = parentIdx[cost[1]]
            }
            // left right 뿐만 아니라 다른 연결된 애들도 모조리 찾아서 바꿔줘야해
            parentIdx.indices.filter{ parentIdx[$0] == oldParent }.forEach{ parentIdx[$0] = newParent }
            // 다리 건설 햇으니까 cost 더해주기
            answer += cost[2]
        }
    }
    return answer
}

private func isCycle(parentArr: [Int], left: Int, right: Int) -> Bool {
    // 양쪽 부모가 같은지 확인
    return parentArr[left] == parentArr[right] ? true : false
}

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