프로그래머스 - 섬 연결하기 [탐욕법(Greedy)]

문제 설명:

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

---

문제 예시:

n	costs	result
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

CopyRight: Programmers

---

문제 해결:

def solution(n, costs):
    costs.sort(key=lambda x: x[2])
    main_group = {costs[0][0]}
    answer = 0
    
    while len(main_group) < n:
        for i in range(len(costs)):
            s, e, w = costs[i]
            
            if s in main_group and e in main_group:
                continue
            
            if s in main_group or e in main_group:
                main_group.add(s)
                main_group.add(e)
                answer += w
                costs.remove(costs[i])
                break
    return answer

모든 값을 비교하면서 최적 값을 넣고 찾았다면 break 하고 다시 while문을 돌려서 최적의 값을 비교하고 찾아낸다.

이때, main_group에 값이 없어야 하며 만약 있더라도 모두가 있으면 안된다.

 

맨 처음에는 weight가 존재하므로 kruskal 방식으로 풀려고 하였지만 weight 비교를 하기가 너무 까다로웠다.

또한, kruskal의 미숙함도 한 몫한 것으로 보인다.

따라서, kruskal을 쓸 때의 예시를 보여주겠다.

 

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

여기서는 ancestor로 linked list가 자기 자신으로 향하는 방식으로 initialize를 한 후에 값을 비교합니다.

만약 둘이 서로 같다면 (이미 연결된 상태) 이때는 건너뜁니다.

그 후 bridges 개수로 완료되었는지 아닌지 확인한 후에 n-1이면 (다 연결된 상태) 그만 둡니다.