[프로그래머스] 섬 연결하기 파이썬 풀이

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

프로그래머스

---

1. 풀이

• costs 리스트를 건설 비용 기준 오름차순 정렬하자

가장 적은 건설 비용으로 모두를 통행할 수 있게 해야 한다. 따라서 다리를 연결할 때 일단 건설 비용이 가장 적은 것부터 고려할 수 있도록 건설 비용을 기준으로 오름차순 정렬해주자.

 

 

• 섬이 어디 섬과 연결되어 있는지 표현하자 (부모 섬)

bridges와 room이라는 리스트를 사용했다. bridges는 연결된 부모 섬을 나타내고, room은 2차원 배열로 부모 섬에 연결된 모든 섬 번호를 저장한다.

 

(좌) 주어진 다리, (우) 최소 비용으로 건설한 다리

 

예를 들어 위와 같은 상황이라고 하자. 왼쪽처럼 costs 정보가 주어지고, 오른쪽처럼 섬들을 연결할 계획이다.

 

초기 상태

 

초기 상태이다. 처음엔 섬들이 연결되어 있지 않기 때문에 각 섬의 대표 섬은 자신이고, 또 자신밖에 존재하지 않는다.

 

[3, 4, 1]과 [,0, 1, 2] 연결

 

이제 [0, 4, 2]를 연결할 차례이다. 이때 bridges[4] = 3이므로, room[3]에 접근해서 room[3]에 있는 모든 섬들을 방문하면서 연결된 부모 섬을 0으로 옮겨주자.

 

[0, 4, 2] 연결

 

이제 [2, 3, 2]를 연결해야 한다. 마찬가지로 brdiges[3] = 0이므로, room[0]의 모든 섬에 접근해서 부모 섬을 2로 바꿔주자.

 

완성이다! 이 로직을 그대로 코드로 작성하면 된다.

 

 

 

 

2. 정답 코드

def solution(n, costs):
    costs.sort(key = lambda x: x[2])  # 건설 비용 기준 오름차순 정렬
    
    bridges = [i for i in range(n)]  # 연결된 섬 (parents)
    room = [[i] for i in range(n)]  # 섬에 연결된 섬들
    
    answer = 0  # 건설 비용
    made = 0  # 만들어진 다리 개수
    
    for x, y, cost in costs:
        x = bridges[x]
        y = bridges[y]
        
        if x == y: continue
        
        # y 섬에 있는 섬들을 모두 x 섬으로 옮김
        while room[y]:
            k = room[y].pop()
            room[x].append(k)
            bridges[k] = x

        answer += cost
        made += 1
        
        if made == n - 1:
            break

    return answer