[백준] 7562번 나이트의 이동

💡문제접근

• 나이트가 이동할 수 있는 경우를 계산하여 시작점에서 도착점까지 도달하는데 필요한 거리를 계산하는 문제다.

• 체스판에서 나이트는 위와 같은 형태의 움직임으로만 이동할 수 있다. 따라서 방향을 나타내는 배열에 8개의 순서쌍을 넣어서 방향을 잡고 체스판의 범위 내에서만 이동가능한 조건을 추가해 코드를 작성하면 쉽게 해결이 가능한 문제였다.

💡코드(메모리 : 34200KB, 시간 : 1780ms)

from collections import deque
import sys
input = sys.stdin.readline

def BFS(cx, cy, dx, dy):
    queue = deque()
    queue.append((cx, cy))
    visited[cx][cy] = True
    graph[cx][cy] = 1
    sx = [-2, -2, -1, 1, 2, 2, 1, -1]
    sy = [-1, 1, 2, 2, 1, -1, -2, -2]
    while queue:
        x, y = queue.popleft()
        if x == dx and y == dy:
            print(graph[dx][dy] - 1)
            return

        for i in range(8):
            nx = x + sx[i]
            ny = y + sy[i]
            if nx < 0 or nx >= I or ny < 0 or ny >= I:
                continue
            if 0 <= nx < I and 0 <= ny < I and not visited[nx][ny]:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx, ny))

T = int(input())
for _ in range(T):
    I = int(input())
    graph = [[0] * I for _ in range(I)]
    visited = [[False] * I for _ in range(I)]
    cx, cy = map(int, input().strip().split())
    dx, dy = map(int, input().strip().split())
    BFS(cx, cy, dx, dy)

💡소요시간 : 9m