[programmers] Level4. 지형이동

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

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

풀이 방법

• 먼저 group을 나눠야 함.

  • BFS로 파이썬 list를 사용해 구현.

• 두 그룹 사이의 높이 차를 구해야 함.

  • dictionary를 사용.
  • key는 (group1, group2) (group1 < group2)
  • value는 두 그룹의 높이 차이
  • 계산을 최소화하기 위해, (0,0)을 시작으로 오른쪽, 아래쪽으로만 나아가며 연산 수행함.

• 최소한의 비용으로 그룹을 합쳐줘야 함.

  • 앞서 구한 dictionary를 value를 기준으로 오름차순 정렬.

  • key, value를 반복문으로 접근하면서 두 그룹을 합쳐줌

  • union_find 알고리즘 적용.

    from collections import defaultdict

def union_find(g1, g2, root):
    # g2 root를 g1 root로 포함시켜줌.
    g1_r = find_root(g1, root)
    g2_r = find_root(g2, root)
    root[g2_r] = g1_r

def find_root(x, root):
    if x == root[x]:
        return x
    else:
        # 찾으면서 root compression
        r = find_root(root[x], root)
        root[x] = r
        return r

# 상하좌우
di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

def calculate_two_group_height(land, visited, table):
    n = len(land)
    for i in range(n):
        for j in range(n):
            ii = i + 1
            jj = j + 1

            if ii <= n-1 and visited[i][j] != visited[ii][j]:
                group1 = min(visited[i][j], visited[ii][j])
                group2 = max(visited[i][j], visited[ii][j])
                table[(group1, group2)] = min(table[(group1, group2)], abs(land[i][j] - land[ii][j]))

            if jj <= n-1 and visited[i][j] != visited[i][jj]:
                group1 = min(visited[i][j], visited[i][jj])
                group2 = max(visited[i][j], visited[i][jj])
                table[(group1, group2)] = min(table[(group1, group2)], abs(land[i][j] - land[i][jj]))


def solution(land, height):
    answer = 0
    n = len(land)
    visited = [[0 for _ in range(n)] for _ in range(n)]
    group = 1
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0:
                queue = [(i, j)]
                while queue:
                    qi, qj = queue.pop(0)
                    visited[qi][qj] = group
                    for d in range(4):
                        ii = qi + di[d]
                        jj = qj + dj[d]
                        if 0 <= ii <= n-1 and 0 <= jj <= n-1 \ # 다음 step이 land 범위 안
                        and visited[ii][jj] == 0 \ # 아직 방문하지 않은 지점
                        and abs(land[qi][qj] - land[ii][jj]) <= height\ # height차이
                        and (ii, jj) not in queue: 
                            queue.append((ii, jj))
                group += 1

    table = defaultdict(lambda : float('inf'))
    calculate_two_group_height(land, visited, table)

    table = sorted(table.items(), key=lambda x:x[1])

    root = {i : i for i in range(1, group)}
    for (g1, g2), height in table:
        if find_root(g1, root) != find_root(g2, root):
            union_find(g1, g2, root)
            # g2를 g1 root로 포함시키고, height 높여줌.
            answer += height

    return answer