[🥲 프로그래머스] 섬 연결하기 - 그리디 알고리즘

https://programmers.co.kr/learn/courses/30/lessons/42861

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

 

나의 풀이

def solution(n, costs):
    costs.sort(key=lambda x:x[2]) # 비용이 작은 순대로 정렬
    all_island = [i for i in range(n)] # 모든 섬
    
    answer = 0
    now = costs.pop(0) # 맨 처음 costs를 뺀다
    while all_island: 
        cur_island = now[0] # 현재섬
        next_island = now[1] # 다음섬
        answer += now[2] # 비용 답안
        
        now = [999, 999, 999]
        for i in range(len(costs)): # 다음 섬이 costs[i][0]과 같고 비용이 가장 적은 경우 찾기
            if costs[i][0] == next_island:
                if now[2] > costs[i][2] and costs[i][1] in all_island:
                    now = costs[i]
                    print(now)
         
         # 그 후 현재섬을 all_island에서 빼주려고 했다.
         # 가장 작은 비용을 가진 섬을 연결연결해서 빼기... 근데 이게 아닌 것 같음!!!!!

 

결국 다른 사람들은 어떤 방식으로 풀었나 살펴보니

대부분의 사람들이 크루스칼 알고리즘을 사용한듯 하다

 

크루스칼 알고리즘은

네트워크의 정점을 최소비용으로 연결하는 것이라고 한다!

 

간단하게 알고리즘을 정리해보면

1. 비용을 오름차순으로 연결

2. 싸이클이 생기지 않게끔 연결 (새로운 간선이 이미 다른 간선에 연결되어 있으면 pass)

 

# 2차 시도 - 25점
def solution(n, costs):
    costs.sort(key=lambda x:x[2]) # 비용이 작은 순대로 정렬
    cycle = []
    
    answer = 0
    while costs:
        cost = costs.pop(0)
        pre = 0 
        dest = 0
        for c in cycle:
            if cost[0] in c:
                pre = 1
            if cost[1] in c:
                dest = 1
        # 두 노드모두 cycle에 속해 있으면 탈락
        if pre == 1 and dest == 1:
            continue
        # 아니면 더해줌
        else:
            cycle.append([cost[0], cost[1]])
            answer += cost[2]
        
    return answer

 

다른사람  풀이

def solution(n, costs):
    # kruskal algorithm
    ans = 0
    costs.sort(key = lambda x: x[2]) # cost 기준으로 오름차순 정렬
    routes = set([costs[0][0]]) # 경로 연결한 노드 집합
    while len(routes)!=n: # 모든 노드 방문하면 끝난다.
        for i, cost in enumerate(costs):
            # 둘 다 route에 이미 있는 경우 pass 
            if cost[0] in routes and cost[1] in routes:
                continue
            if cost[0] in routes or cost[1] in routes:
                routes.update([cost[0], cost[1]]) # 해당 값 추가
                ans += cost[2] # 비용 더하기
                break
    return ans

 

내 풀이는 왜 안되지?????????ㅜㅜ