KnightL on a Chessboard

Problem Link
https://www.hackerrank.com/challenges/knightl-on-chessboard/problem?isFullScreen=true

✅ Problem Summary

직각 형태로 움직일 수 있는 체스 말(knight)을 이용하여, $n\times n$ 크기의 행렬에서 $(0, 0)$ 부터 $(n-1, n-1)$ 까지 말의 최소 이동 횟수를 구하는 문제

• 아래에 해당하는 모든 경우의 수를 구하여 행렬 형태로 출력해야 함 ($KnightL(i,j)$에 해당하는 값을 행렬 $(i,j)$에 넣어서 출력)

---

🧮 Applied Theory & Algorithm

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

그림 출처: Wikipedia

---

📑 My Answer

• 모든 테스트 케이스 통과

def bfs(n, i, j):
    checkVisit = [[0] * n for _ in range(n)]
    queue = [[0, 0]]
    dx, dy = [i, i, -i, -i, j, -j, j, -j], [j, -j, j, -j, i, i, -i, -i]
    while queue:
        px, py = queue.pop(0)
        for p in range(8):
            nx, ny = px + dx[p], py + dy[p]
            if 0 <= nx < n and 0 <= ny < n and checkVisit[nx][ny] == 0:
                queue.append([nx, ny])
                checkVisit[nx][ny] = checkVisit[px][py] + 1
    return -1 if checkVisit[n - 1][n - 1] == 0 else checkVisit[n - 1][n - 1]


def knightlOnAChessboard(n):
    result = [[0] * (n - 1) for _ in range(n - 1)]
    for i in range(1, n):
        for j in range(i, n):
            val = bfs(n, i, j)
            result[i - 1][j - 1], result[j - 1][i - 1] = val, val
    return result

📌 코드 구현 설명

• 반복문을 사용하여 발생할 수 있는 모든 경우를 탐색함 (BFS 알고리즘 이용)
  • $KnightL(i,j) = KnightL(j,i)$ 이므로, 절반만 탐색
• BFS 함수에서 $Knight$의 방문 노드 확인 및 이동 횟수 계산을 위해 checkVisit 이라는 행렬을 생성
  • $Knight$는 다음 위치인 checkVisit[i][j] 의 값이 0일 때만 이동하며, 이동한 이후에는 checkVisit[i][j]에 이전 단계까지의 $Knight$ 이동 횟수에 1을 더하여 저장
• 모든 경우를 탐색한 후, 최종적으로 checkVisit[n-1][n-1]의 값이 0이 아니라면 checkVisit[n-1][n-1] 에 저장된 값을 return, 0이라면 -1을 return

---

💼 Takeaway

• BFS 문제 유형에 대해 감을 잡게 되었다.

---