BOJ - 7562

백준 문제 링크
나이트의 이동

❓접근법

1. BFS를 사용했다.
2. 나이트가 이동할 수 있는 방향을 새로 정해줘야한다.
3. dx = [-2,-1,1,2,-2,-1,1,2],
   dy = [1,2,2,1,-1,-2,-2,-1]로 설정했다.
4. queue에 좌표와 distance를 넣어줘서 나이트가 이동할 때마다 새로운 좌표에 전 좌표의 distance + 1을 넣어줬다.
5. 출발한 좌표가 목표 좌표에 도달하면 break해서 반복문을 탈출한다.

👌🏻코드

from collections import deque
T = int(input())
answer = []

for _ in range(T):
    N = int(input())
    
    lst = [[0] * N for _ in range(N)]
    dx = [-2,-1,1,2,-2,-1,1,2]
    dy = [1,2,2,1,-1,-2,-2,-1]

    start_x, start_y = map(int, input().split())
    end_x, end_y = map(int, input().split())


    queue = deque()
    queue.append((start_x, start_y,0))

    visited = set()
    visited.add((start_x, start_y))

    
    while queue:
        x,y,distance = queue.popleft()

        if (x,y) == (end_x, end_y):
            answer.append(distance)
            break

        for d in range(8):
            nx = x + dx[d]
            ny = y + dy[d]

            if (0 <= nx < N) and (0 <= ny < N) and ((nx,ny) not in visited):
                queue.append((nx,ny,distance + 1))
                visited.add((nx,ny))
                
for i in answer:
    print(i)