[프로그래머스] 지형 이동 - Python

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

 

문제 설명

N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.

이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.

각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• land는 N x N크기인 2차원 배열입니다.
• land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
• land의 원소는 각 격자 칸의 높이를 나타냅니다.
• 격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
• height는 1 이상 10,000 이하인 자연수입니다.

---

입출력 예

land	height	result
[[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]]	3	15
[[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]]	1	18

입출력 예 설명

입출력 예 #1

각 칸의 높이는 다음과 같으며, 높이차가 3 이하인 경우 사다리 없이 이동이 가능합니다.

위 그림에서 사다리를 이용하지 않고 이동 가능한 범위는 같은 색으로 칠해져 있습니다. 예를 들어 (1행 2열) 높이 4인 칸에서 (1행 3열) 높이 8인 칸으로 직접 이동할 수는 없지만, 높이가 5인 칸을 이용하면 사다리를 사용하지 않고 이동할 수 있습니다.

따라서 다음과 같이 사다리 두 개만 설치하면 모든 칸을 방문할 수 있고 최소 비용은 15가 됩니다.

• 높이 5인 칸 → 높이 10인 칸 : 비용 5
• 높이 10인 칸 → 높이 20인 칸 : 비용 10

입출력 예 #2

각 칸의 높이는 다음과 같으며, 높이차가 1 이하인 경우 사다리 없이 이동이 가능합니다.

위 그림과 같이 (2행 1열) → (1행 1열), (1행 2열) → (2행 2열) 두 곳에 사다리를 설치하면 설치비용이 18로 최소가 됩니다.

---

풀이 1. 크루스칼 알고리즘을 이용한 방법

우선 사다리 없이 이동 가능한 구간을 그룹화시킨다. 각 칸을 차례로 방문하면서 아직 방문하지 않은 칸으로부터 상, 하, 좌, 우를 기준으로 BFS 탐색을 시도한다. 사다리 없이 이동이 가능한 구간을 같은 번호로 묶어 준다. (코드에서 해당 로직의 결과는 groups에 담긴다.)

 

이어서 그룹과 그룹 사이에 맞닿는 지점들 중 최솟값을 찾는다. 이 경우, 완전 탐색을 진행하게 되는데 현재 칸에서 상하좌우를 살폈을 때 현재 칸과 다른 그룹 번호가 존재한다면 해당 구간을 맞닿는 지점으로 판단하고, 그 위치에서의 비용을 구한다. 비용은 defaultdict를 사용하여 값을 저장하는데 이 딕셔너리의 키는 맞닿은 두 구간의 번호이다. 1번 그룹과 2번 그룹이 마주한다면 (1, 2)가 키가 되는 것이다. 키에 대한 값으로는 비용이 저장되는데 매번 저장되어있는 비용과 현재 구한 비용을 비교해 최솟값을 기록하게 한다. (코드에서 해당 로직의 결과는 groups_weights에 담긴다.)

 

위 작업으로 인해 그룹 간 각각의 가중치로 이어져있는 그래프 형태를 얻게 되었다. 마지막으로 최소 비용으로 이 그래프의 모든 노드를 잇는 MST(최소비용신장트리)를 구해야한다. MST를 구하기 위해 크루스칼(Kruskal) 알고리즘을 이용한다. (크루스칼 알고리즘에 대한 상세한 설명은 여기) 

 

크루스칼 알고리즘에서는 해당 간선을 추가할 때 사이클이 발생하는지 여부를 체크하여, 사이클이 발생한다면 간선을 추가하지 않도록 한다. 사이클 발생 여부를 확인하기 위해 유니온-파인드(Union-Find) 알고리즘을 사용한다. 두 그룹의 root값이 동일하다면 두 그룹은 이미 이어져있음을 의미한다. 이어져 있다면 건너뛰고, 이어져 있지 않은 경우는 처음으로 잇는 것이기 때문에 해당 그룹 간의 가중치를 value에 추가한다.

 

import collections
import math

# 그룹화를 시킬때 사다리 없이 방문할 수 있는 칸을 bfs로 탐색한다.
def bfs(land, height, groups, x, y, group_number):
    move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    queue = collections.deque([(x, y)])
    groups[x][y] = group_number

    while queue:
        now = queue.popleft()

		# 상, 하, 좌, 우 이동
        for i in range(4):
            new_x = now[0] + move[i][0]
            new_y = now[1] + move[i][1]

			# 범위 밖을 벗어나는 경우는 pass
            if new_x < 0 or new_y < 0 or new_x >= len(groups) or new_y >= len(groups[0]) or groups[new_x][new_y] != 0:
                continue
			
            # 사다리 없이 방문 가능한 경우에는 큐에 추가하고, 해당 칸에 그룹번호를 입력시킨다.
            if abs(land[new_x][new_y] - land[now[0]][now[1]]) <= height:
                queue.append((new_x, new_y))
                groups[new_x][new_y] = group_number


# 그룹과 그룹 사이의 가중치의 최솟값을 구한다.
def get_groups_wieghts(land, groups, height):
    move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    
    # 그룹과 그룹 사이의 가중치를 저장할 딕셔너리
    # 기본값으로 inf를 둔다.
    # 키 : (그룹a, 그룹b)
    # 값 : 최소 가중치
    weights = collections.defaultdict(lambda: math.inf)

    for i in range(len(groups)):
        for j in range(len(groups[0])):
            now = groups[i][j]
            for dx, dy in move:
                new_x, new_y = i + dx, j + dy

				# 범위를 벗어나는 경우 pass
                if new_x < 0 or new_y < 0 or new_x >= len(groups) or new_y >= len(groups[0]) or groups[new_x][new_y] == now:
                    continue

                dist = abs(land[new_x][new_y] - land[i][j])
                
                # 그룹과 그룹 사이 놓을 수 있는 사다리 중 가장 적은 비용을 저장
                weights[(now, groups[new_x][new_y])] = min(
                    dist, weights[(now, groups[new_x][new_y])])

    return weights

# 유니온파인드 알고리즘의 find 메소드
# root[x]의 값이 본인이 아니라는 것은
# 종속되어 있는(=이어져있는) 다른 노드가 존재함을 의미
def find(x, root):
    if x == root[x]:
        return x
    else:
        r = find(root[x], root)
        root[x] = r
        return r

# 유니온파인드 알고리즘의 union 메소드
# x와 y의 각각의 뿌리를 찾아서 하나로 합쳐준다.
def union(x, y, root):
    x_root = find(x, root)
    y_root = find(y, root)
    root[y_root] = x_root

# 크루스칼 알고리즘
def kruskal(group_weights, groups):
    sum = 0
    roots = {_: _ for _ in range(1, groups)} # {1:1, 2:2, 3:3 ... }

    for (x, y), value in group_weights:
        if find(x, roots) != find(y, roots):
            sum += value
            union(x, y, roots)
        if len(roots.items()) == 1:
            return sum
    return sum


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

    groups = [[0 for _ in range(col)] for _ in range(row)]

    group_number = 1
    for i in range(row):
        for j in range(col):
            if groups[i][j] == 0:
                bfs(land, height, groups, i, j, group_number)
                group_number += 1

    groups_weights = get_groups_wieghts(land, groups, height)
    
    # 가중치 값이 작은 순서로 정렬
    groups_weights = sorted(groups_weights.items(), key=lambda x: x[1])

    answer = kruskal(groups_weights, group_number)
    return answer

[참고]

[프로그래머스/Python] 지형 이동

 

이 방법은 그룹화시키는 단계와 그룹 간 사다리를 놓는 비용 값을 찾는 단계를 분리시킨 방법이다. O(n^2)이 걸리는 로직을 두 번씩 수행하는 셈이다.

 

 

 

풀이 2. 우선순위 큐를 이용한 방법

파이썬의 우선순위 큐 모듈인 heapq를 이용해서도 풀이가 가능하다. 큐에는 (사다리비용, x좌표, y좌표) 형태로 값을 담으며, (0, 0, 0)으로 탐색을 시작한다.

 

land의 각 칸을 차례로 방문해 상,하,좌,우의 값과 비교를 한다. 차이가 height보다 작다면 사다리비용은 0으로 두고, 차이가 height보다 크다면 사다리 비용을 차이값으로 두고 큐에 push를 한다.

 

우선순위 큐는 사다리비용을 기준으로 오름차순 정렬을 한다. 때문에 자연스럽게 사다리가 필요한 지점 중 가장 비용이 낮은 값부터 탐색을 하게 되고, 사다리가 필요한 지점 중 비용이 높은 지점을 탐색하려고 할 때는 해당 칸은 이미 방문을 완료된 칸이 되어 있으므로 value에 값이 추가되지 않고 넘어간다.

 

import heapq

def solution(land, height):
    N = len(land)
	
    # 방문 여부를 체크하는 2차원 배열
    visited = [[False for _ in range(N)] for _ in range(N)]
    move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    
    # 큐
    queue = []

    visit_count = 0
    max_count = N * N
    value = 0

	# 탐색 시작 지점을 큐에 넣는다.
    queue.append((0, 0, 0))

    while visit_count < max_count:
    	# 사다리비용, x좌표, y좌표
        val, x, y = heapq.heappop(queue)

		# 이미 방문한 곳이라면 건너뛴다.
        if visited[x][y]:
            continue
        visited[x][y] = True

        visit_count += 1
        value += val

		# 현재 칸의 높이
        current_height = land[x][y]

        for dx, dy in move:
            nx, ny = x + dx, y + dy

            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                continue
			
            # 다음 칸의 높이
            next_height = land[nx][ny]
            
            # 현재 칸과 다음 칸의 높이 차이가 height보다 크다면 사다리가 필요한 시점
            if abs(next_height - current_height) > height:
                heapq.heappush(
                    queue, (abs(next_height - current_height), nx, ny)) # (사다리비용, x좌표, y좌표)
            # 사다리가 필요하지 않은 시점은 사다리비용을 0으로 처리
            # 다음 반복문에서 value += 0 이기 때문에 결과값에 영향을 미치지 않음
            else:
                heapq.heappush(queue, (0, nx, ny))
    return value

[참고]

[프로그래머스] '지형 이동' 알고리즘 풀이 - Python