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

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

프로그래머스

 

2023.07.18 기준 Level 3

 

알고리즘 공부용으로 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

그리디 문제이며 모든 노드(섬)들을 연결할 수 있도록 엣지(다리)를 만들고 이 때 필요한 비용이 최소일 때를 구하는 문제였습니다.

 

각 노드들을 연결하면 그래프를 형성하게 됩니다.

이때 각 노드들을 모두 연결하면서 사이클을 갖지 않는 최소 부분 그래프가 생기게 되는데 이것을 신장 트리(Spanning Tree)라고 합니다.

 

상단 그래프에 대한 4개의 신장 트리 예시 (출처: https://limecoding.tistory.com/123)

 

그리고 각 엣지에 가중치가 부여된 그래프에서 만들 수 있는 신장 트리 중 가중치의 합에 가장 낮은 신장 트리를 최소 신장 트리(Minimum Spanning Tree)라고 합니다. 줄여서 MST라고도 부릅니다! 

최소 신장 트리는 (d)이다. (출처: https://limecoding.tistory.com/123)

 

결국 이 문제는 이 최소 신장 트리를 구하는 문제였습니다!

(그래프에 대한 개념이 가물가물해서 고생을... 다시 제대로 공부해야겠다..!)

 

이 문제를 풀기 위해서는 각 섬들로 구성된 최소 신장 트리를 만들어야 하는데 최소 신장 트리를 찾는 알고리즘 중 대표적인 것이 크루스칼 알고리즘(Kruskal's Algorithm)입니다!!

 

크루스칼 알고리즘

1. 엣지들을 가중치(비용)에 따라 오름차순으로 정렬한다.
2. 정렬한 엣지들을 하나씩 확인하면서 엣지를 연결했을 때 사이클이 발생하지는 않는지 검사한다.
   
   1. 사이클이 발생하지 않는다면 최소 신장 트리에 포함시킨다. (결과값에 추가)
   2. 사이클이 발생한다면 최소 신장 트리에 포함시키지 않는다.

 

생각보다 간단한 구조입니다.

최소 비용을 위해 가중치를 기준으로 오름차순으로 정렬하는 것으로 시작합니다. 당연하게도 가중치가 낮은 엣지들로 구성해야 최소 비용이 되기 때문입니다..!

 

그 다음 2번의 과정이 중요한데 각 엣지들을 최소 신장 트리에 포함시킬지 판단하는 부분입니다.

이 때 사이클이 생기면 신장 트리가 아니게 되기 때문에 사이클이 생기지 않도록 해야합니다.

 

해당 엣지를 포함시켰을 때 사이클이 생기는지를 파악하기 위해서는 Union-Find 알고리즘을 사용하면 됩니다!!!

Union-Find 알고리즘은 두 노드가 서로 같은 그래프에 속하는지를 판별하는 알고리즘입니다.

 

만약 엣지를 구성하는 두 노드가 Find 알고리즘을 돌려서 같은 그래프에 속한다고 결과가 나오면 두 노드를 연결하는 엣지를 최소 신장 트리에 추가했을 때 사이클이 발생하게 됩니다.

따라서 Find 알고리즘을 써서 두 노드가 다른 그래프에 속한다고 결론이 나올 때에만 해당 엣지를 트리에 추가하는 방식입니다!!

 

Union-Find 알고리즘

• 서로소 집합, 상호 배타적 집합 (Disjoint-Set)이라고도 합니다.
• Find 연산과 Union 연산으로 구성됩니다.
• Find
  • 노드 A가 어떤 집합에 포함되어 있는지 찾는 연산입니다.
  • 부모 노드를 리턴합니다.
• Union
  • 노드 A가 속한 집합과 노드 B가 속한 집합을 합치는 연산입니다.

그래프 예시

위와 같은 그래프에서 Find 연산을 실행하면 다음과 같은 과정이 이어집니다.

 

1. parent 배열을 생성하여 각 노드들의 부모를 기록하도록 합니다. (초기값으로 자기 자신을 부모로 설정합니다.)

index	0	1	2	3	4	5
parent 배열	0	1	2	3	4	5

2. 각 그래프의 연결 관계가 데이터로 들어왔을 때 이를 배열에 기록하면 다음과 같이 될 수 있습니다. (데이터의 값에 따라 배열이 다르게 저장 될 수 있으며 아래의 표는 예시입니다.)

index	0	1	2	3	4	5
parent 배열	1	2	2	3	1	3

3. find(&parent, 4)을 실행하면 다음과 같은 작업이 발생합니다.

1. parent[4]에 접근하여 1을 얻는다.
2. parent[1]에 접근하여 2를 얻는다.
3. parent[2]에 접근하여 2를 얻는다.
4. index와 value가 2로 같기 때문에 find함수는 2를 리턴하고 종료된다.

4. 즉, 4의 부모 노드는 2가 됩니다. (부모를 계속 거슬로 올라가며 최종 부모를 찾았음)

 

 

이제 Union 연산을 실행했을 때의 예시를 보여드리겠습니다.

union(&parent, 4, 5)를 실행하면 다음과 같은 작업이 발생합니다.

 

1. find(&parent, 4) 를 실행하여 4의 부모가 2라는 것을 확인
2. find(&parent, 5) 를 실행하여 5의 부모가 3이라는 것을 확인

둘 중 하나의 부모 노드의 부모를 다른쪽 부모 노드로 바꾸면 두 그래프가 연결되게 됩니다.

여기서는 5의 부모를 4의 부모로 바꾸어서 두 집합을 합치겠습니다.

(정확히는 5의 부모인 3의 parent 값을 4의 부모로 바꾸는 작업입니다.)

 

index	0	1	2	3	4	5
parent 배열	1	2	2	2	1	3

 

두 그래프가 합쳐져서 1개의 그래프가 된 모습

 

풀이

1. 크루스칼 알고리즘을 사용하기 위해서 필요한 Union-Find 알고리즘을 먼저 구현합니다.

// 유니온 파인드

/// 부모 노드를 찾는다.
fileprivate func find(_ parent: inout [Int], _ index: Int) -> Int {
    if parent[index] == index {
        return index
    }
    
    parent[index] = find(&parent, parent[index])
    return parent[index]
}

/// 두 노드가 속한 집합을 합친다. => 하나의 그래프로 만든다. (두 노드의 부모 노드끼리 연결하면 결국 두 집합을 합치는 꼴이 된다.)
fileprivate func union(_ parent: inout [Int], _ a: Int, _ b: Int) {
    let parentOfA = find(&parent, a)
    let parentOfB = find(&parent, b)
    
    if a < b {
        parent[parentOfB] = parentOfA
    } else {
        parent[parentOfA] = parentOfB
    }
}

parent는 배열이기 때문에 값 타입입니다. 우리는 함수에서 이 parent 배열의 복사본이 아닌 원본에 접근해야 하기 때문에 inout 키워드를 사용하여 참조 타입처럼 사용했습니다. 

 

2. 크루스칼 알고리즘을 이용해 문제를 해결합니다.

fileprivate func solution(_ n:Int, _ costs:[[Int]]) -> Int {
    
    // 간선을 오름차순으로 정렬
    let costs = costs.sorted {
        $0[2] < $1[2]
    }
    
    var result = 0
    var parent = [Int]()
    
    // 자기 자신을 부모 노드로 설정하여 parent 배열 초기화
    for i in 0..<n {
        parent.append(i)
    }
    
    for cost in costs {
        let node1 = cost[0]
        let node2 = cost[1]
        if find(&parent, node1) != find(&parent, node2) {
            union(&parent, node1, node2)
            result += cost[2]
        }
    }
    
    return result
}

 

마무리

그래프에 대한 개념과 최소 신장 트리에 대한 개념이 모두 필요했습니다.

최소 신장 트리를 구하기 위해 크루스칼 알고리즘을 사용했고 이를 위해 Union-Find 알고리즘이 필요했습니다.

 

해당 알고리즘들에 대한 사전 지식이 있는 사람이라면 생각보다 쉽게 문제를 풀 수 있겠지만 그렇지 않은 사람으로서 직접 아이디어를 떠올려 풀기에는 어려운 문제라고 생각합니다.

 

레벨 3의 문제이기 때문에 단순히 1개의 알고리즘을 적용하여 푸는 것이 아니라 여러 가지의 개념들과 알고리즘이 복합적으로 어우러져야 해결할 수 있었습니다!