[HackerRank] KnightL on a Chessboard

def findMinimum(a,b,n):
    area = [[0]*n for _ in range(n)]
    visited = [[False]*n for _ in range(n)]
    nx = [a, a, -a, -a, b, b, -b, -b]
    ny = [b, -b, b, -b, a, -a, a, -a]
    queue =[[0,0]]
    
    visited[0][0] = True
    
    while queue:
        v = queue.pop(0)
        for i in range(8):
            temp_x = v[0] + nx[i]
            temp_y = v[1] + ny[i]
            
            if temp_x >= 0 and temp_x < n and temp_y >=0 and temp_y < n:
             if not visited[temp_x][temp_y]:
                if area[temp_x][temp_y] == 0:
                    area[temp_x][temp_y] = area[v[0]][v[1]] + 1
                else:
                    area[temp_x][temp_y] = min(area[temp_x][temp_y], area[v[0]][v[1]] + 1)
                queue.append([temp_x,temp_y])
                visited[temp_x][temp_y] = True
                
    if area[n-1][n-1] == 0:
        return -1
    else:
        return area[n-1][n-1]

def knightlOnAChessboard(n):
    # Write your code here
    result = [[0]*(n-1) for _ in range(n-1)]
    for i in range(1,n):
        for j in range(1,n):
            result[i-1][j-1]=findMinimum(i,j,n)
    return result

이번 문제는 주어진 n x n 크기의 체스판에서 장기말이 이동할 수 있는 범위가 (1, 1) ~ (n-1, n-1)으로 주어졌을 때, (n-1, n-1) 위치까지 이동할 수 있는 최소 이동 횟수를 구하는 문제이다. 이때 해당 자리에서 (n-1, n-1) 위치까지 이동할 수 없다면 -1 을 저장해야 한다.

 

이 문제는 해석하는데 시간이 오래 걸리긴 했지만, 결국 이동할 수 있는 범위가 주어졌을 때 (0, 0)에서 (n-1, n-1)까지 이동하는 횟수의 최솟값을 구하는 문제이다.

 

이 문제를 이해하고 나서 생각난 해결법은 DFS나 BFS 알고리즘을 사용하여 (n-1, n-1)까지 도착하는 경우의 수를 구하는 것이었는데, 최소 이동 횟수를 유지해야 하는 이유 때문에 BFS를 사용하였다.

 

또한, 주어진 범위로 이동할 수 있는 경우의 수는 nx = [a, a, -a, -a, b, b, -b, -b] ny = [b, -b, b, -b, a, -a, a, -a] 로 총 8가지 이기 때문에 8가지 이동 경로를 모두 이동해가며 아직 이동하지 않았다면 현재까지의 이동 횟수 + 1을 저장하였고, 이동한 적이 있었다면 현재까지의 이동 횟수 + 1 와 저장된 이동 횟수의 최솟값을 저장해주었다.

 

for i in range(1,n):
        for j in range(1,n):
            result[i-1][j-1]=findMinimum(i,j,n)

그리고 마지막으로 이동할 수 있는 범위는 1 <=  a, b < n 이므로 (1, 1)부터 (n-1, n-1)까지 Burte Force, 즉 모든 범위를 완전 탐색을 해보아야 한다는 의미이고, 따라서 2중 반복문을 통해 모든 범위를 체크해주었다.

 

처음에 deque 라이브러리를 사용하였더니 오류가 발생하여 구글링을 통해 deque를 사용하지 않고 큐 자료구조를 사용할 수 있는 방법을 사용하였다. (queue = [[0,0]], v = queue.pop(0)) ⭐️