Red Knight's Shortest Path

Problem Link
https://www.hackerrank.com/challenges/red-knights-shortest-path/problem?isFullScreen=true

✅ Problem Summary

아래 그림과 같이 여섯 가지의 이동을 할 수 있는 특수 체스 말을 주어진 위치 $(i_{start},j_{start})$ 에서 목적지 $(i_{end},j_{end})$ 까지의 최소 이동 횟수와, 해당 이동 횟수에 해당하는 체스 말의 움직임을 출력하는 문제

• 경로가 겹치는 경우, UL > UR > R > LR > LL > L 를 우선 순위로 하여 경로 출력
• 만약 불가능하다면 Impossible 출력

그림 출처: HackerRank Red Knight's Shortest Path

---

🧮 Applied Theory & Algorithm

1. 너비 우선 탐색 (Breadth-First Search)

그림 출처: Wikipedia

---

📑 My Answer

• 모든 테스트 케이스 통과

def bfs(n, pos, dtn):
    matrix = [[0]*n for _ in range(n)]
    dx = [-2, -2, 0, 2, 2, 0]
    dy = [-1, 1, 2, 1, -1, -2]
    moveName = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
    queue = [(pos[0], pos[1], [])]
    while queue:
        tx, ty, path = queue.pop(0)
        if (tx, ty) == dtn:
            return (matrix[tx][ty], path)
        for i in range(6):
            nx, ny = tx + dx[i], ty + dy[i]
            if 0<=nx<n and 0<=ny<n and matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[tx][ty] + 1
                queue.append((nx, ny, path+[moveName[i]]))
    return -1

def printShortestPath(n, i_start, j_start, i_end, j_end):
    result = bfs(n, pos=(i_start, j_start), dtn=(i_end, j_end))
    if result == -1:
        print("Impossible")
    else:
        print(result[0])
        print(*result[1], end=' ')

📌 코드 구현 설명

• 최소 이동 횟수를 구하기 위해 가능한 모든 경우의 수를 탐색해야 한다는 점과, 우선 순위 경로가 있다는 점(queue를 활용하기 때문에)에서 BFS 알고리즘 사용
• 0으로 표시된 방문하지 않은 위치(노드)로만 이동이 가능하며, 목적지에 도착할 때 까지 UL > UR > R > LR > LL > L 순서 대로 경로를 탐색
  • 현재 방문한 위치 matrix[nx][ny]에는 이전 위치까지의 이동 횟수 matrix[tx][ty]에 1을 더하여 저장
• bfs 함수를 통해 목적지에 무사히 도착하면 해당 결과를, 아니라면 -1을 return하여 답 출력

---