프로그래머스 지형 이동

프로그래머스 Lv.4 최소 신장 트리로 풀이한 문제인 지형 이동 문제입니다.

 

해당 문제의 링크입니다.

코딩테스트 연습 - 지형 이동

 

문제의 골자는 서로 이동할 수 없는 지형들을 하나의 노드로 보고, 각각의 노드들 사이의 간선의 가중치를 하나의 노드에서 다른 노드로 이동하기 위한 사다리 높이의 최소값으로 계속해서 갱신해주는 것입니다. 그렇게 간선들을 만들어준 다음에는 가중치에 대해서 오름차순으로 간선들을 정렬하고, 유니온 파인드를 활용하여 최소 신장 트리를 구하면 됩니다.

 

<풀이>

 

def solution(land, height):
    graph = {}
    ans = 0
    i, j = len(land), len(land[0])
    dx, dy = (0, 0, 1, -1), (1, -1, 0, 0)
    separated = [[0]*j for _ in range(i)]

    def separate():
        cur = 1
        for r in range(i):
            for c in range(j):
                if separated[r][c]:
                    continue
                separated[r][c] = cur
                stack = [(r, c)]
                while stack:
                    x, y = stack.pop()
                    for d in range(4):
                        nx, ny = x+dx[d], y+dy[d]
                        if nx < 0 or nx >= i or ny < 0 or ny >= j:
                            continue
                        if separated[nx][ny] and separated[nx][ny] < cur:
                            if (separated[nx][ny], cur) in graph:
                                graph[(separated[nx][ny], cur)] = min(
                                    graph[(separated[nx][ny], cur)], abs(land[x][y]-land[nx][ny]))
                                continue
                            graph[(separated[nx][ny], cur)] = abs(
                                land[x][y]-land[nx][ny])
                            continue
                        if not separated[nx][ny] and abs(land[nx][ny] - land[x][y]) <= height:
                            stack.append((nx, ny))
                            separated[nx][ny] = cur
                cur += 1
        return cur

    def getP(a):
        if p[a] == a:
            return a
        p[a] = getP(p[a])
        return p[a]

    def uniP(a, b):
        a, b = getP(a), getP(b)
        if a > b:
            p[a] = b
        else:
            p[b] = a

    cur = separate()
    p = list(range(cur))
    edges = [(i, j, d) for (i, j), d in graph.items()]

    for i, j, d in sorted(edges, key=lambda x: x[-1]):
        if getP(i) != getP(j):
            uniP(i, j)
            ans += d
    return ans

 

seperate 함수는 서로 다른 지형들을 구별해주는 함수입니다. 핵심은 seperated라는 방문을 기록하기 위한 2차원 배열을 약간 변형하여 node를 저장하는 것입니다. 이를 통해 어떤 노드에서 어떤 노드로 이동하는 최소 값이 어떻게 되는 지를 지속적으로 갱신하여 최소값을 찾을 수 있습니다. 또한, 최종적으로 node의 갯수를 return해주는데, 이를 활용해 유니온 파인드를 진행하게 됩니다. 물론, 이를 활용하지 않고 최대값인 90001을 활용해도 됩니다. 

getP와 uniP는 유니온 파인드를 위한 함수이며, 서로 다른 서로소인 부분집합을 getP를 통해서 알아낼 수 있고, 서로소인 부분집합을 uniP를 통해서 합쳐줄 수 있습니다. 그렇게 서로소인 부분집합만을 낮은 비용부터 접근하여 연결해주면 최소 신장 트리를 완성할 수 있습니다.

 

<채점 결과>

 

'''
정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.4MB)
테스트 2 〉	통과 (0.07ms, 10.3MB)
테스트 3 〉	통과 (0.05ms, 10.5MB)
테스트 4 〉	통과 (0.10ms, 10.3MB)
테스트 5 〉	통과 (0.07ms, 10.3MB)
테스트 6 〉	통과 (0.10ms, 10.3MB)
테스트 7 〉	통과 (0.07ms, 10.4MB)
테스트 8 〉	통과 (0.07ms, 10.4MB)
테스트 9 〉	통과 (0.10ms, 10.3MB)
테스트 10 〉	통과 (0.09ms, 10.3MB)
테스트 11 〉	통과 (0.08ms, 10.3MB)
테스트 12 〉	통과 (0.07ms, 10.5MB)
테스트 13 〉	통과 (0.08ms, 10.3MB)
테스트 14 〉	통과 (0.21ms, 10.3MB)
테스트 15 〉	통과 (0.99ms, 10.4MB)
테스트 16 〉	통과 (9.93ms, 10.8MB)
테스트 17 〉	통과 (38.68ms, 13.8MB)
테스트 18 〉	통과 (39.23ms, 13.5MB)
테스트 19 〉	통과 (32.34ms, 12.5MB)
테스트 20 〉	통과 (181.17ms, 21.9MB)
테스트 21 〉	통과 (196.97ms, 22.6MB)
테스트 22 〉	통과 (388.59ms, 46.3MB)
테스트 23 〉	통과 (395.35ms, 48.3MB)
테스트 24 〉	통과 (137.95ms, 17.7MB)
테스트 25 〉	통과 (144.51ms, 15.9MB)
테스트 26 〉	통과 (436.64ms, 44.9MB)
테스트 27 〉	통과 (387.07ms, 45MB)
테스트 28 〉	통과 (395.61ms, 43.6MB)
테스트 29 〉	통과 (366.57ms, 42.4MB)
테스트 30 〉	통과 (388.81ms, 46.2MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0
'''