파이썬으로 체스판 위 나이트의 공격 여부 확인하기

문제 개요

2차원 이진 행렬이 하나의 직사각형 체스판을 나타낸다고 가정해 보겠습니다. 행렬에서 0은 빈 칸을 의미하고, 1은 나이트(knight)가 놓여 있는 칸을 의미합니다. 체스의 나이트는 가로로 두 칸, 세로로 한 칸 이동하거나, 반대로 세로로 두 칸, 가로로 한 칸 이동할 수 있습니다.

이번 글에서 다룰 문제는 바로 체스판 위의 나이트들 중 서로 공격하고 있는 쌍이 존재하는지 판별하는 것입니다.

예를 들어 입력이 다음과 같다면,

(1, 1) 위치의 나이트와 (2, 3) 위치의 나이트가 서로 공격 가능한 거리에 있으므로 출력은 True가 됩니다.

해결 알고리즘

이 문제는 다음 단계를 통해 해결할 수 있습니다.

• 행렬의 행 수(row)와 열 수(col)를 구합니다.
• 모든 칸을 순서대로 탐색하며, 값이 0이 아닌 칸(나이트가 있는 칸)을 찾습니다.
• 나이트를 발견하면 해당 위치 기준으로 (r+1, c-2), (r+1, c+2), (r+2, c-1), (r+2, c+1) 네 곳을 확인합니다.
• 확인 대상 좌표가 행렬 범위 안에 있고, 그 자리에 다른 나이트가 있다면 즉시 True를 반환합니다.
• 모든 칸을 확인했는데도 공격 관계를 찾지 못했다면 False를 반환합니다.

여기서 주목할 점은 8개 방향을 모두 검사하지 않고 아래쪽과 오른쪽 방향 4곳만 확인해도 된다는 것입니다. 왼쪽이나 위쪽에 있는 나이트와의 공격 관계는 이미 그 나이트를 탐색할 때 검증되었기 때문에, 중복 검사를 피할 수 있습니다.

구현 예제

class Solution:
   def solve(self, A):
      row, col = len(A), len(A[0])
      for r in range(row):
         for c in range(col):
            if A[r][c]:
               for nr, nc in ((r+1, c-2), (r+1, c+2), (r+2, c-1), (r+2, c+1)):
                  if 0 <= nr < row and 0 <= nc < col and A[nr][nc]:
                     return True
      return False

ob = Solution()
mat = [[0,0,0,0,0],
       [0,1,0,0,0],
       [0,0,0,1,0]]
print(ob.solve(mat))

입력

[[0,0,0,0,0],
[0,1,0,0,0],
[0,0,0,1,0]]

출력

True

복잡도 분석

이 알고리즘은 행렬의 모든 칸을 한 번씩 순회하며 각 나이트마다 최대 4개의 인접 후보 좌표만 확인하므로, 시간 복잡도는 O(N × M)(N은 행 수, M은 열 수)입니다. 추가 공간 사용 없이 원본 행렬만 참조하므로 공간 복잡도는 O(1)로 매우 효율적입니다.