섬 연결하기

섬 연결하기
탐욕법(Greedy)
1687명 완료

최소 신장 트리(Kruskal Algorithm)로 풀 수 있는 문제입니다. 
이 알고리듬을 공부하신 적 있으시다면 어렵지 않게 풀 수 있을 겁니다. 

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

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

문제를 읽어보면..
주어진 배열을 비용을 적게 드는 순서대로 연결합니다.
(정렬이 필요, 탐욕 알고리듬이죠.)
이때 이미 연결된 조합은 제외해야 합니다.
(Union-Find 알고리듬, 아래 코드에서는 path리스트와 find 함수로 구현)
사이클이 생기는 조합은 제외해야 합니다.
(root1 == root2 면 따라가다가 한 군데에서 만나는 겁니다.) 

def solution(n, costs):
    def find(node):
        if paths[node] != node:
            paths[node] = find(paths[node])
        return paths[node]

    paths = [each for each in range(n)]
    answer = 0
    costs.sort(key=lambda each: each[2])
    for node1, node2, cost in costs:
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            paths[max(root1, root2)] = min(root1, root2)
            answer += cost
    return answer

max에서 한 번 min에서 한번 두 번 비교를 하는데...
if else로 한 번에 비교하는 게 정석이겠지만
저게 가독성이 더 좋아서
라기 보단 한 줄이라도 더 줄이려고.. 

테스트 1 〉	통과 (0.04ms, 10.8MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.06ms, 10.8MB)
테스트 4 〉	통과 (0.06ms, 10.8MB)
테스트 5 〉	통과 (0.06ms, 10.8MB)
테스트 6 〉	통과 (0.08ms, 10.8MB)
테스트 7 〉	통과 (0.09ms, 10.7MB)
테스트 8 〉	통과 (0.05ms, 10.7MB)

 

아래처럼 족보없는 깔끔한 코딩을 하고 싶었는데... 
중간에 계속 꼬여서 정석적인 알고리듬의 기억을 빌렸습니다..  

def solution(n, costs):
    answer, linked = 0, {costs[0][0]}
    costs.sort(key=lambda each: each[2])
    while len(linked) != n:
        for i, (node1, node2, cost) in enumerate(costs):
            if (node1 in linked) ^ (node2 in linked):
                linked.update((node1, node2))
                costs.pop(i)
                answer += cost
                break
    return answer

^는 xor입니다. 
가독성(줄여쓰기)을 위해 튜플을 적극적으로 이용했습니다. 

테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.05ms, 10.8MB)
테스트 4 〉	통과 (0.05ms, 10.7MB)
테스트 5 〉	통과 (0.05ms, 10.8MB)
테스트 6 〉	통과 (0.06ms, 10.7MB)
테스트 7 〉	통과 (0.07ms, 10.7MB)
테스트 8 〉	통과 (0.05ms, 10.7MB)