[프로그래머스 lv4] 지형 이동(BFS)

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

프로그래머스

 

 

문제설명

 

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 이하인 자연수입니다.

 

문제 해결 방법

 

BFS를 활용해서 문제를 풀었다. 그런데 BFS를 할 때, 고려해줘야 하는게 있었다. 

바로 사다리 설치비용이다. 문제에서 요구한대로 최소한의 사다리 설치 비용을 산출해내야 되기 때문에, 좌표에서 상, 하, 좌, 우 이동시 발생할 수 있는 사다리 설치 비용에 대해서 우선순위를 매겨야한다. 이때 heapq 우선순위 큐를 활용하여 문제를 해결했다. 

 

 

코드 구현

 

BFS, heapq 자료구조를 이용해 풀이한 코드

import heapq 

def solution(land, height):
    answer = 0
    # 좌표 움직임을 위한 배열
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    
    #시작 좌표
    startX, startY = 0, 0
    
    # 방문 여부 확인을 위한 배열
    visited = [[False] * len(land) for _ in range(len(land[0]))]
    
    heap = []
    
    
    def bfs(stratX, startY):
        answer = 0
        heapq.heappush(heap, [0, startX, startY]) # 비용, startX, startY
        
        while len(heap) != 0:
            cost, x, y = heapq.heappop(heap)
            #print('cost', cost)
            
            
            if visited[y][x] == False:
                visited[y][x] = True
                
                answer += cost
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    
                    # 새로운 좌표가 정사각 격자 형태의 지형을 벗어나는지 체크
                    if ny >= len(land) or nx >= len(land[0]) or ny < 0 or nx < 0:
                        continue
                    
                    if abs(land[y][x]-land[ny][nx]) <= height:
                        newcost = 0
                        
                    else:
                        newcost = abs(land[y][x]-land[ny][nx])
                        
                    heapq.heappush(heap, [newcost, nx, ny])
        return answer
        
        
    answer = bfs(startX, startY)          
    #print(answer)
    
    return answer

 

 

 

BFS구현 및 deque로 구현하려다가 실패한 코드

 

from collections import deque

def solution(land, height):
    answer = 0
    realAnswer = 0
    # 좌표 움직임을 위한 배열
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    
    #시작 좌표
    startX, startY = 0, 0
    
    # 방문 여부 확인을 위한 배열
    visited = [[False] * len(land) for _ in range(len(land[0]))]
    
    check = [[10000] * len(land[0]) for _ in range(len(land))]
    
    print(visited)
    
    queue = deque()
    
    def bfs(stratX, startY):
        
        #시작하는 좌표를 큐에 넣고, 
        
        # 큐에 값이 있으면 큐에서 값을 꺼내어 방문 처리를 한다. 
        # 꺼낸 값에 인접한 값 중에서 방문하지 않은 좌표인지 확인한 후, 
        # 방문하지 않았으면 큐에 넣는다.
        
        queue.append([startX, startY])
        nx = 0
        ny = 0
        
        while len(queue) != 0:
            x, y = queue.popleft()
            visited[y][x] = True
            print('')
            print('x, y', x, y)
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                print('i', i, 'nx, ny:', nx, ny)
                # 새로운 좌표가 정사각 격자 형태의 지형을 벗어나는지 체크
                if ny >= len(land) or nx >= len(land[0]) or ny < 0 or nx < 0:
                    print('?1')
                    continue
                
                if visited[ny][nx] == True:
                    print(visited)
                    print('?2')
                    continue
                
                print('nx, ny', nx, ny, 'x', 'y', x, y)
                print(land[y][x], land[ny][nx])
                if abs(land[y][x]-land[ny][nx]) <= height:
                    check[ny][nx] = abs(land[y][x]-land[ny][nx])
                    print('input', nx, ny)
                    queue.append([nx, ny])
#                 else:
#                     if check[ny][nx] > abs(land[y][x]-land[ny][nx]):
#                         check[ny][nx] = abs(land[y][x]-land[ny][nx])
                    
#                     print('input', nx, ny)
#                     queue.append([nx, ny])
    
    
    bfs(startX, startY)
    check[0][0]=0    
    print('check', check)           
        
    
    
    
    
    
    
    return answer

 

 

시간/공간 복잡도

 

최악의 경우 O(N^2log(N^2))

 

최적화 및 개선 / 어려웠던 점

 

진짜 BFS에서 좌표 문제는 항상 헷갈리는 것 같다. 

이 문제를 풀면서 깨달은 것은 이차원배열에서 x, y 좌표의 값을 구하고 싶으면

 

이차원배열명[y][x]

이렇게 호출해야 한다는 점이다. 

 

그리고 heapq와 deque의 사용처에 대해서 분명히 알게됐다. 

heapq는 deque보다 자료의 우선순위를 매겨야 할 때 사용하는 것이 적절하다. 

반대로 자료의 우선순위를 매겨야할 때 deque를 사용하는 것은 적절치 않다.