백준 7562 나이트의 이동

나이트의 이동

계획

• BFS
• 숨바꼭질 문제처럼 이미 간 곳은 큐에 포함 안하도록 할 것

import sys
from collections import deque
input = sys.stdin.readline
tc = int(input())

# 나이트 이동 위치
dx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]


def bfs(x, y, endX, endY):
    if x == endX and y == endY:
        return 0
    count = 0
    queue = deque([[x, y, count]])
    visited[y][x] = 1
    while queue:
        v = queue.popleft()
        x = v[0]
        y = v[1]
        count = v[2]
        for idx in range(8):
            # print(queue)
            nx = x + dx[idx]
            ny = y + dy[idx]
            if nx < 0 or ny < 0 or nx >= i or ny >= i or visited[ny][nx] == 1:
                continue
            if nx == endX and ny == endY:
                return count + 1
            queue.append([nx, ny, count + 1])
            visited[ny][nx] = 1


for _ in range(tc):
    i = int(input())
    visited = []
    for _ in range(i):
        visited.append([0] * i)

    x, y = map(int, input().split())
    endX, endY = map(int, input().split())

    print(bfs(x, y, endX, endY))

• nameerror가 뜨길래 뭔가했더니 import sys를 자꾸 빼먹음