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

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

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로 최소가 됩니다.

 

 

알고리즘 분석

 

• 나의 풀이 ( 시간 초과 )

from collections import defaultdict
from math import inf

DIR = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 위, 아래, 왼쪽, 오른쪽 

def generator(land, height, data, N, board):
    Y, X = data  # 현재 좌표 
    com_val = land[Y][X]  # 현 좌표의 높이 

    for y, x in DIR:  # 4방향으로 이동 
        move_y, move_x = y+Y, x+X  # 이동했을 때 y, x 좌표 
        # 이동한 좌표가 범위 안인지 확인 and 이미 방문했는지 확인 
        if 0 <= move_x < N and 0 <= move_y < N and not board[move_y][move_x]:
            if abs(land[move_y][move_x] - com_val) <= height: # 높이의 차이가 height와 같거나 작을 때
                yield [move_y, move_x]

# 다음 그룹을 찾아줌 
def next_group(N, board):  
    for i in range(N):
        for j in range(N):
            if not board[i][j]:
                return [i, j]

# 사다리 없이 방문 가능한 곳끼리 그룹핑 
def grouping(land, height): 
    N = len(land)  # land의 길이 
    group = defaultdict(list)  # 딕셔너리로 그룹 구분 
    board = [[False for _ in range(N)] for _ in range(N)]  # 방문 여부, True면 방문했음 

    cnt = 1  # 그룹의 넘버 
    queue, board[0][0], group[cnt] = [[0, 0]], True, [[0, 0]]  # 초기값 지정 

    while queue: 
        data = queue.pop(0)

		# 현 좌표에서 다음 방문할 좌표를 구한다
        for next_data in generator(land, height, data, N, board): 
            y, x = next_data
            board[y][x] = True
            group[cnt].append(next_data)
            queue.append(next_data)
		
        # 더 이상 그룹에 추가할 곳이 없다면 다음 그룹을 만든다 
        if not queue:
            cnt += 1  
            ng = next_group(N, board)
            if ng:
                y, x = ng
                board[y][x] = True
                group[cnt] = [[y, x]]
                queue.append([y, x])

    return group


def solution(land, height):
    answer = 0
    group = grouping(land, height)  # 그룹핑된 결과를 반환 
    queue = [group.pop(1)] # key가 1인 그룹을 queue에 넣음 

    while queue:
        min_height, key = inf, 0  
        g_one = queue.pop(0) 
        for g_two in group.keys(): # g_one과 비교할 그룹들 
            for y1, x1 in g_one: # g_one의 y, x 좌표 
                for y2, x2 in group[g_two]: # g_two의 y, x 좌표 
                    if (y1-y2, x1-x2) in DIR: # 둘의 차이가 DIR 안에 있으면 
                        candi = abs(land[y1][x1] - land[y2][x2]) # 후보값 candi
                        if candi < min_height: # candi가 min_height보다 작다면 
                            min_height = candi # 후보값이 min_height를 대신함 
                            key = g_two # min_height가 있는 그룹의 key 값 
        if key: # key가 0이 아니면 
            answer += min_height
            queue.append(g_one + group.pop(key))
    return answer

 

 코드를 작성하면서 부터 느꼈지만 for문이 너무 많이 들어갔기 때문인지 시간초과가 발생했네요. 

그래도 오답이 없는게 그나마 다행인듯... 

 

이 코드는 land에서 사다리 없이 갈 수 있는 부분끼리 그룹핑을 해줬습니다.

그 이후에 그룹끼리 비교해서 가작 적은 height로 사다리를 설치할 수 있는 

그룹끼리 다시 한 그룹으로 만든 후에 다른 그룹과 비교하는 방식을 사용했습니다. 

 

 

 

• Most 1의 풀이

import heapq


def solution(land, height):
    N = len(land)  # land의 길이

    visited = [[False for _ in range(N)] for _ in range(N)]  # 방문했는지
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 이동할 방향
    queue = [] # 뀨?

    queue.append((0, 0, 0))  # 큐에 초기값 지정
    visit_count = 0  # 방문 횟수
    max_count = N * N  # 최대 방문 가능 횟수
    value = 0  # 사다리 설치비용

    while(visit_count < max_count):
        print(queue)
        v, y, x = heapq.heappop(queue)
        if visited[y][x]:  # 이미 방문했다면
            continue # 넘긴다
        visited[y][x] = True  # 방문 완료

        visit_count += 1  # 방문 횟수 + 1
        value += v  # 사다리 설치 비용 추가

        c_height = land[y][x]  # 현 좌표의 height
        for ay, ax in move:
            ny, nx = y + ay, x + ax  # 이동한 좌표의 y, x
            if move2(ny, nx, N, visited):  # 이동 가능한지 체크
                n_height = land[ny][nx]  # 이동한 좌표의 height

                if abs(n_height - c_height) > height:  # 사다리가 필요한 경우 필요한 비용을 값으로 줌 
                    heapq.heappush(queue, (abs(n_height - c_height), ny, nx))
                else:  # 사다리 없이 방문 가능한 좌표는 비용은 0을 준다
                    heapq.heappush(queue, (0, ny, nx))
    return value

 

세상은 넓고 천재는 많은거 같습니다.

 

heap을 이용한 풀이입니다. 

heap은 pop을 사용할 시 무조건 최솟값을 반환하게 되어있는 성질을 이용했습니다. 

 

사다리 없이 방문이 가능한 좌표의 경우 

첫번째 값에 0을 주어서 

사다리 없이 방문 가능한 모든 좌표를 방문하고 나면 

 

그 다음에 사다리를 설치했을 때 최소의 비용으로 방문 가능한 좌표가 오게됩니다. 

그 좌표에서 다시 한번 사다리 없이 방문 가능한 좌표를 찾게되고 

heap의 성질을 이용해서 그 좌표들이 heap의 맨 앞에 위치하게 되면서

그 값을 최우선적으로 연산하게 됩니다. 

 

 

 

 

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