문제 출처: 프로그래머스 LV3 탐욕범 섬 연결하기
풀이:
문제설명
- n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
제한사항
- 섬의 개수 n은 1 이상 100 이하입니다.
- costs의 길이는 ((n-1) * n) / 2이하입니다.
- 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
- 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
- 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
- 연결할 수 없는 섬은 주어지지 않습니다.
코드 풀이
def solution(n, costs):
answer = 0
costs.sort(key = lambda x: x[2]) # 비용기준으로 오름차순 정렬
connect = set([costs[0][0]]) # 연결을 확인하는 집합 시작점
# Kruskal 알고리즘으로 최소 비용 구하기
while len(connect) != n:
for cost in costs:
if cost[0] in connect and cost[1] in connect:
continue
if cost[0] in connect or cost[1] in connect:
connect.update([cost[0], cost[1]])
answer += cost[2]
break
return answercosts 를 비용기준으로 오름차순 정렬하고. 제일 작은 곳에 시작점을 넣어준다.
while 문이 n이 아닌경우는 모든 곳이 연결하기 직전까지이다.
첫 번째 if문으로 연결된 경우를 체크하고
두 번째 if문 으로 연결이 안된경우 연결을 시켜주면서 비용을 추가해주고, 그 다음에 break 를 시켜주면 된다.
이 방법은 set을 사용한 크루스탈 알고리즘이고 다음은 진짜 근본 크루스탈 알고리즘을 보여주겠다.
def find(parent, x):
if parent[x] != x: # 자기 자신이 아닌경우 다른 노드에 연결된 경우
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, x, y):
x_root = find(parent, x)
y_root = find(parent, y)
if x_root<y_root :
parent[y_root] = x_root
else :
parent[x_root] = y_root
def solution(n, costs):
costs = sorted(costs, key=lambda x: x[2])
parent = [i for i in range(n)]
res = 0
for (x, y, z) in costs:
if find(parent, x) != find(parent, y):
union(parent, x, y)
res += z
return res
입력값은 아래처럼 주어진다고 하겠다. 이유는 뒤에서 설명하겠다.
입력값 :
7, [[2, 3, 7], [3, 6, 13], [3, 5, 23], [5, 6, 25], [0, 1, 29], [1, 5, 34], [1, 2, 35], [4, 5, 53], [0, 4, 75]]step 1.
def find(parent, x):
if parent[x] != x: # 자기 자신이 아닌경우 다른 노드에 연결된 경우
parent[x] = find(parent, parent[x])
return parent[x]find 함수이다 각 숫자의 최 상단 부모노드를 찾는것이다 부모가 같은데 연결을 해주면 삼각형이 나와 싸이클이 생성된다.
step2.
def union(parent, x, y):
x_root = find(parent, x)
y_root = find(parent, y)
if x_root<y_root :
parent[y_root] = x_root
else :
parent[x_root] = y_root부모의 값이 다를때 합쳐주는것이다. 부모가 다를때 union은 값이 작은곳으로 합쳐지게 된다. 그것을 코드로 작성하면 저렇다.
step3.
def solution(n, costs):
costs = sorted(costs, key=lambda x: x[2])
parent = [i for i in range(n)]
res = 0
for (x, y, z) in costs:
if find(parent, x) != find(parent, y):
union(parent, x, y)
res += z
return res먼저 비용을 기준으로 오름차순을 해준다.
그러면 costs는 [[2, 3, 7], [3, 6, 13], [3, 5, 23], [5, 6, 25], [0, 1, 29], [1, 5, 34], [1, 2, 35], [4, 5, 53], [0, 4, 75]] 이다.
parent는 처음 우선 다 자기자신을 가르키고있다.
정렬된 costs 에서 값을 가져와서 부모값을 비교하면서 찾는다.
처음에 2,3,7 을 뽑는다고 해보자 그러면 x는 2 y는 3 비용은 7 이다. 지금 parent 는 다 자기자신이므로 2와 3의 부모는 자기자신을 가르키고있다. 그러면 부모의 값이 다르지 않는가? 그러니 둘은 합칠 수 있는 조건이 되면서 union 함수가 실행된다.
그러면 union함수에서 작은 값으로 부모 노드를 저장한다고 했으니 2와 3 중에 작은 2가 3의 부모 노드가 되는것이다.
근데 이 코드를 다 실행해보고 parent를 뽑아보면
[0, 0, 0, 2, 0, 0, 2])이렇게 나와서 생각이 많아 질 수 있다. 포문에 parent를 뽑아보면이렇게 나온다.
[0, 1, 2, 2, 4, 5, 6]
[0, 1, 2, 2, 4, 5, 2]
[0, 1, 2, 2, 4, 2, 2]
[0, 0, 2, 2, 4, 2, 2]
[0, 0, 0, 2, 4, 2, 2]
[0, 0, 0, 2, 0, 0, 2]그러면 여기서 또 의문이 생길 수 있다. 4번째 줄을보면 3번노드도 2번을 가르키고, 4번노드도 2번을 가르키는데 왜 3번노드만 0 번을 가르키는지
또 6번노드도 2를 가르켰고, 7번노드도 2를 가르켰는데 왜 6번노드의 부모만 0이고 7번만 노드의 부모는 0 이 아닌지. 모두 0 으로 나오는것이 바로 서로소 집합에서 경로 압축 기법을 사용하는 것인데,
경로압축기법을 사용하면 모두다 0을 가르키는데 저렇게 나오는 이유는 단순히 순서 문제이다 마지막에 for문을 통해 find로 부모를 찾아보면 다 0 이 나온다.
서로소 집합이란 : 공통 원소가 없는 집합이다.
서로소 집합은 서로 다른 두 개의 집합을 병합하는 연산(Union)(Merge)과 집합의 원소가 어떤 집합에 속해 있는지 판단하는 연산(Find)을 기반으로 구현되기 때문에, Union-Find 혹은 Merge-Find Set이라고도 불린다.
각 집합을 대표하는 부모가 다른 부모로 편입되는것이다. 위 코로 말하자면 3번노드와, 6번노드가 2번노드로 편입한 것이다.
설명하기 힘들어 내가 이해한 곳의 링크를 남기도록 한다.
https://sskl660.tistory.com/71?category=845232
[Java]서로소 집합(Disjoint Set)(Union-Find)(Merge-Find Set)
*서로소 집합(Disjoint Set) -> 서로소 집합 자료구조는 상호 배타적으로 이루어진 집합(서로소 집합 : 공통 원소가 없는 두 집합)을 효율적으로 표현하기 위해 만들어진 자료구조이다. -> 서로소 집
sskl660.tistory.com
[알고리즘] Disjoint Sets(서로소 집합)
💡 Disjoint Sets(서로소 집합)? 서로소 집합이란, 공통 원소가 없는 두집합을 의미한다. 왼쪽 그림에서 집합 A와 B는 서로소 관계이고, 오른쪽 그림에서 집합 A와 B는 서로소 관계가 아니다. 서로소
doing7.tistory.com
댓글