[프로그래머스 lv 3] 섬 연결하기

사용 언어 - Python3

문제 - 섬 연결하기

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

프로그래머스

 

 

정답

크루스칼 알고리즘

가중치를 기준으로 정렬 후 유니온 + 파인드

 

가중치를 기준으로 정렬  = costs.sort(key=lambda x:x[2])

내 노드에서 연결 된 모든 선 확인 = 부모 찾기 _find(x)

같은 집합으로 묶어주기 = 사이클 안생기게 처리 _union(a,b)

 

def _find(x):
    while par[x] != x: # 부모가 있다면
        x = par[x] # 부모로 업데이트
    return x

def _union(a,b):
    # 가장 윗 부모로 업데이트
    a = _find(a)
    b = _find(b)
    
    if a == b: # 사이클 X
        return
    
    # 순위가 더 높은 것이 부모
    if rank[a] < rank[b]:
        par[a] = b
    elif rank[b] < rank[a]:
        par[b] = a
    else:
        par[a] = b
        rank[b] += 1
        
par = [i for i in range(101)] # 부모
rank = [0 for _ in range(101)] # union 최적화

def solution(n, costs):
    answer = 0
    
    costs.sort(key = lambda x:x[2])
    
    for i in range(len(costs)):
        a = costs[i][0]
        b = costs[i][1]
        weight = costs[i][2]
        
        a = _find(a)
        b = _find(b)
        if a != b:
            _union(a,b)
            answer += weight
        else:
            continue
    
    return answer

 

 

2. 연결 가능한 bridge 만들기

bridge = set([0])

섬x 또는 섬y 둘중 하나만 bridge에 있을 때에만 answer += c, bridge.add(없는 섬)

from collections import deque

def solution(people, limit):
    answer = 0
    stack = deque(sorted(people,reverse=True)) # 내림차순 정렬
    
    while len(stack) > 1:
        if stack[0] + stack[-1] <= limit:
            answer += 1 # 같이 보트태우고 둘다 pop
            stack.pop()
            stack.popleft()
        else:
            answer += 1
            stack.popleft() # 더 큰 것만 없애기
    if stack: # 남아있는 사람 한명 있다면 보트태우기
        answer += 1

    return answer

 

 

 

 

레퍼런스

유사한 크루스칼 문제

https://rladuddms.tistory.com/449

[백준] 1197번 최소 스패닝 트리 (프림, 크루스칼)

 

다른 방법 문제풀이

https://velog.io/@rnjsrntkd95/%ED%83%90%EC%9A%95%EB%B2%95-%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0-Level-3-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4

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