프로그래머스 - 지형 이동

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

접근

백준에 있는 삼성기출문제 '다리 만들기2'와 아주 유사한 문제입니다.

1. BFS로 구역을 나누고
2. 각 구역을 연결하는 모든 다리를 구합니다.
3. kruskal 알고리즘을 사용합니다.

구현

전반적으로 시뮬레이션 느낌이 강했고, 짜잘하게 신경써주어야 될 부분이 있긴 했습니다.

그냥 구현하느라 위에서 1과 2를 나눴는데

실제로는 구역을 나누면서 다른구역과 마주쳤는데, 사다리를 놓아야 할 상황일때를 구해버리면 되긴합니다.

다음은 코드 전문입니다.

from collections import deque,defaultdict


def solution(land, height):
    answer = 0
    row = len(land)
    col = len(land[0])

    visited = []



    vi_co = 0

    for i in range(row):
        temp = []
        for j in range(col):
            temp.append(0)
        visited.append(temp)

    for i in range(row):
        for j in range(col):
            if visited[i][j] != 0:
                continue
            else:
                deq = deque()
                deq.append([i, j])
                vi_co += 1

                visited[i][j] = vi_co

                while len(deq) != 0:
                    r = deq[0][0]
                    c = deq[0][1]
                    deq.popleft()

                    if (r + 1) < row and (r + 1) >= 0 and c < col and c >= 0:
                        if abs(land[r][c] - land[r + 1][c]) <= height and visited[r + 1][c] == 0:
                            deq.append([r + 1, c])
                            visited[r + 1][c] = vi_co
                    if (r - 1) < row and (r - 1) >= 0 and c < col and c >= 0:
                        if abs(land[r][c] - land[r - 1][c]) <= height and visited[r - 1][c] == 0:
                            deq.append([r - 1, c])
                            visited[r - 1][c] = vi_co
                    if r < row and r >= 0 and (c + 1) < col and (c + 1) >= 0:
                        if abs(land[r][c] - land[r][c + 1]) <= height and visited[r][c + 1] == 0:
                            deq.append([r, c + 1])
                            visited[r][c + 1] = vi_co
                    if r < row and r >= 0 and (c - 1) < col and (c - 1) >= 0:
                        if abs(land[r][c] - land[r][c - 1]) <= height and visited[r][c - 1] == 0:
                            deq.append([r, c - 1])
                            visited[r][c - 1] = vi_co

    dir = [ [1,0] , [-1,0] , [0,1], [0,-1] ]
    cost = defaultdict(lambda :10000)
    is_connected = []
    for r in range(row):
        for c in range(col):
            for dr,dc in dir:
                if 0 <= r+dr < row and 0 <= c + dc < col:
                    if visited[r+dr][c+dc] < visited[r][c]:
                        continue
                    elif visited[r+dr][c+dc] > visited[r][c]:
                        cost[(visited[r][c],visited[r+dr][c+dc])] = min(cost[(visited[r][c],visited[r+dr][c+dc])],abs(land[r][c] - land[r+dr][c+dc]))


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


    global root
    root = [-1]
    for i in range(1, vi_co + 1):
        root.append(i)

    for (s,e),c in cost:
        root_x = u_find(s)
        root_y = u_find(e)

        if root_x != root_y:
            u_union(s,e)
            answer+=c


    return answer


def u_find(x):
    global root

    if root[x] == x:
        return x
    else:
        root[x] = u_find(root[x])
        return root[x]

def u_union(x,y):
    global root

    x = u_find(x)
    y = u_find(y)

    root[y] = x