프로그래머스 코딩테스트 고득점 Kit_탐욕법(Greedy)_섬 연결하기

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

• kruskal알고리즘 사용
• 가중치가 가장 작은 간선부터 확인
  => 해당 간선이 cycle을 발생하지 않을 경우 연결
  => 부모노드가 다를 경우 cycle을 발생하지 않음
  => 연결 정보 connection을 따라 올라가며 node번호와 값이 같을 때 node의 값이 부모노드 값 (이때, connection의 인덱스는 node번호 값은 해당 node번호의 부모 노드 번호)
• 간선을 연결하고 연결정보를 갱신 해 줘야 함
  => ex)
  다음과 같이 node0과 node2이 연결 되어있음
  connection = [0, 1, 0]
  다음과 같은 상황에서 node1와 node2을 연결할 때,
  node3과 연결되어있는 node1의 connection 정보를 갱신하여 다음과 같이 저장해야함
  connection = [1, 1, 0]

구현 코드 👇

def get_p(connection, node):
    if connection[node] == node:
        return node
    return get_p(connection, connection[node])

def solution(n, costs):
    costs.sort(key = lambda x: x[2], reverse = True)
    connection = [i for i in range(n)]  #연결 정보
    edges = []

    while len(edges) != n - 1:
        i1, i2, cost = costs.pop()
        #부모 노드가 다를 경우 연결 가능
        if get_p(connection, i1) != get_p(connection, i2):
            #연결 정보 갱신
            connection[get_p(connection, i1)] = i2
            edges.append(cost)

    return sum(edges)

---

📝 cycle 생성 여부를 다른 방식으로도 검증 할 수 있다.

다른 풀이 코드👇

#두 섬이 visited에 모두 존재 : 이미 건설한 다리
#두 섬이 visited에 모두 존재하지 X : 이미 연결되어 있는 섬들과 이 두 섬이 연결되지 X
#=> 해당 경우는 반복문을 끝낸 후 다시 반복문을 반복하며 연결
#두 섬 중 하나의 섬만 visited에 존재할 경우 다음과 같이 구현

def solution(n, costs):
    costs.sort(key = lambda x: x[2])
    visited = {costs[0][0]}  #방문 한 섬
    answer = 0
    while len(visited) != n:
        for island1, island2, cost in costs:
            if len({island1, island2} & visited) == 1:
                visited.update([island1, island2])
                answer += cost
                break #노드가 추가 되었으므로 len(visited) != n 조건 확인
                
    return answer