[프로그래머스] 탐욕법 5. 섬 연결하기

문제

https://programmers.co.kr/learn/courses/30/lessons/42861?language=python3

코딩테스트 연습 - 섬 연결하기

---

풀이

최소신장트리 문제인 것 같아 검색해 보았다.

MST 문제에는 크게 두 가지 방법의 해결책이 있는 듯 했다.

• 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복
  Prim의 알고리즘의 시간 복잡도는 O(n^2)
• Kruskal 알고리즘의 시간 복잡도는 O(elog₂e)
• 그래프 내에 적은 숫자의 간선만을 가지는 ‘희소 그래프(Sparse Graph)’의 경우 Kruskal 알고리즘이 적합하고
  그래프에 간선이 많이 존재하는 ‘밀집 그래프(Dense Graph)’ 의 경우는 Prim 알고리즘이 적합하다.
  https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html

이번 문제는 간선이 많아 보이지 않았으므로 크루스칼 알고리즘을 사용하기로 결정했다.

역시나 까먹었기 때문에 검색했다. https://www.youtube.com/watch?v=LQ3JHknGy8c 

 

진짜 풀이

1. costs 정렬

2. union table 생성

3. sortedCosts 비용 적은 순으로 순회

- union table 다르면 작은 값으로 갱신

- answer에 cost 더하기

- 모든 union table 값 같으면 모두 연결되었다는 뜻이므로 break

 

def solution(n, costs):
    answer = 0
    sortedCosts = sorted(costs, key=lambda x: x[2])
    print(sortedCosts)
    unionTable = [i for i in range(n)]
    
    i = 0
    while len(set(unionTable)) != 1: # 모든 유니온테이블 값이 같으면 break
        if unionTable[sortedCosts[i][0]] != unionTable[sortedCosts[i][1]]: # 사이클이 없음
             # 작은 쪽으로 union Table 갱신
            unionTable[sortedCosts[i][1]] = unionTable[sortedCosts[i][0]]
            answer += sortedCosts[i][2]
        i += 1
        if (i > len(costs)):
            break
        
    return answer

알고리즘대로 짰다고 생각했는데 틀렸다

앗 생각해보니까 union find처리를 재귀로 안하고 그냥 해버렸다.

def find(u):
    if u != unionTable[u]:
        unionTable[u] = find(unionTable[u])
    return unionTable[u]

def union(u, v):
    root1 = find(u)
    root2 = find(v)
    unionTable[root2] = root1

def solution(n, costs):
    answer = 0
    costs = sorted(costs, key=lambda x: x[2])
    global unionTable 
    unionTable = [i for i in range(n)]
    edges = 0

    while edges < n-1: # 모든 노드가 연결되면 탈출
        u, v, weight = costs.pop(0)
        if find(u) != find(v):
            union(u, v)
            edges += 1
            answer += weight
    
    return answer

이분 코드 참고해서 수정함 (https://it-garden.tistory.com/411)

---

다른 사람의 풀이

def ancestor(node, parents):
    if parents[node] == node:
        return node
    else:
        return ancestor(parents[node], parents)

def solution(n, costs):
    answer = 0
    edges = sorted([(x[2], x[0], x[1]) for x in costs])
    parents = [i for i in range(n)]
    bridges = 0
    for w, f, t in edges:
        if ancestor(f, parents) != ancestor(t, parents):
            answer += w
            parents[ancestor(f, parents)] = t
            bridges += 1
        if bridges == n - 1:
            break
    return answer

크루스칼 알고리즘인 것 같긴 한데 간단하게 짜신 듯 ,,