백준 1197: 최소 스패닝 트리 (Swift)

서로소를 확인할 수 있는 union-find알고리즘과

이를 이용하여  "무방향 그래프"에서 최소 스패닝트리, 즉 모든 노드를 포함하지만 싸이클이 발생하지 않는 부분 그래프 중 간선의 비용 합이 최소가 되는 경우를 찾아야하는 기본 "크루스칼" 알고리즘 문제이다.

 

파이썬으로는 해당 알고리즘을 많이 작성해보았지만, Swift로 처음 구현하려다보니 막히는 부분이 몇 있었다!

Swift로 코딩 인터뷰를 수행하려면 알아두어야할 꿀 표현들이 들어있는 문제였다.

 

-  1. 1~n까지 자연수가 오름차순으로 위치한 1차원 배열 초기화!

-  2. 2차원 배열 [ (a.0, a.1, a.2), (b.0, b.1, b.2), (c.0, c.1, c.2)]과 같은 형태에서, n번째 원소 기준으로 sort하기

 

위의 두가지 표현을 python에서는

 

- 1. arr = [ i for i in range(1, n+1)]

- 2. arr.sort(key = lambda x: (x[1], x[0]))  --> 2번째 원소 기준 정렬, 같을 경우 1번째 원소 기준으로 정렬 ( 오름차순 )

과 같이 한 줄로 표현했었다.

Swift로 코딩 인터뷰를 준비한 기간이 짧다보니 위의 두 표현을 찾는데 조금 애를 먹었다...

 

그럼 Swift에서는 어떻게 표현했는지 아래의 코드에서 보도록 하자.

 

23 번째 줄을 보면,

## 꿀 표현 1!!!

var parent: [Int] = Array(0...nm[0])

생각보다 간단하게 [0,1,2,3.....nm[0]]의 정수가 오름차순으로 배치된 1차원 배열을 초기화할 수 있었다....

 

## 꿀 표현 2!!!

29번 줄을 보면,

edges.sort{ (a,b) -> Bool in

    return a[2] < b[2]

}

라는 표현이 있다.

이는 edges 배열에 있는 원소를 정렬하면서, 각 원소 내부의 2번 index에 있는 원소를 기준으로 정렬을 하겠다는 의미이다!