[자료구조] [python] Castle on the Grid (deque)

 

Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 

 

www.hackerrank.com/challenges/castle-on-the-grid/problem

Castle on the Grid | HackerRank

 

Deque는 python의 collection 모듈에 구현된 객체/자료형이다. stack과 que의 일반형태의 자료형이며, Deque는 thread-safe (스레드 안전)을 지원하며, 자료의 양방향에서 O(1) 성능으로 원소를 추가하거나 제거할 수 있다. append(), appendleft(),pop(),popleft() 함수를 사용하여 양방향에서 원소를 추가하고 뺄 수 있다. 

 

 

풀이 포인트는 다음과 같다. 먼저, input의 grid를 각 원소별 list로 만들어서 하나의 character를 하나의 원소로 만든다. 2D로 구성된 grid array에 start 점을 0으로 만드는 것으로 시작하여, 이동거리를 직접 계산하여 숫자를 넣는다. 별도로 또다른 array변수로 만들지 않는다. 특정 array index부터 주변을 방문하여, 'X'로 표기 되지 않아 방문 가능한 point들을 모은 points list를 만든다. getPointsFromPoint()에 구현하였다. 특정 점부터 방문 가능한 점들을 탐색할 때, 행 > 열/ 왼>우 순으로 탐색한다. 이후, 원소가 숫자로 표현되어 있지 않은 지점들을 방문하여 '.'로 방문이 가능한 지점이면, Deque에 왼쪽방향에 넣는다. 이는, 선입선출하여 스타트 지점부터 거리를 계산하기 위함이다. 여기에서 거리를 구할 때, 주의해야 할 점이 있다. 당신은 행과 열을 따라서 자유롭게 이동할 수 있으며, 이 때, 한 행을 따라 이동 할 때의 횟수는 어떤 행의 위치든 1의 추가값을 가진다. (문제 설명 중 Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. 이라는 부분 참고) 따라서, (0,0) -> (0.2)로 이동하였을 때의 moves수는 2가 아닌 1의 값을 가진다. 

 

 

from collections import deque
 
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
     
    def __str__(self):
        return "X=%d,Y=%d" % (self.x, self.y)
 
def getPointsFromPoint(N, arr, point):
    x = point.x
    y = point.y
    points = []
     
    while x > 0:
        x -= 1
        if arr[x][y] == 'X':
            break
        points.append(Point(x,y))
     
    x = point.x
    while x < N-1: 
        x += 1
        if arr[x][y] == 'X': 
            break
        points.append(Point(x,y)) 
     
    x = point.x 
    while y > 0:
        y -= 1
        if arr[x][y] == 'X':
            break
        points.append(Point(x,y))
     
    y = point.y
    while y < N-1:
        y += 1
        if arr[x][y] == 'X':
            break
        points.append(Point(x,y))
         
    return points


def minimumMoves(grid, startX, startY, goalX, goalY):
    
    start = Point(startX, startY)
    end = Point(goalX, goalY)
    arr = [list(x) for x in grid]
    N = len(grid)
    
    q = deque([start])
    arr[start.x][start.y] = 0
    
    while q:
        current_point = q.pop()
        current_distance = arr[current_point.x][current_point.y]
        points = getPointsFromPoint(N, arr, current_point)
        
        for p in points:
            if arr[p.x][p.y] == '.':
                arr[p.x][p.y] = current_distance + 1
                q.appendleft(p)
                if p.x == end.x and p.y == end.y:
                    return current_distance + 1
    return -1