7562_나이트의 이동

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

 

역시 bfs를 이용한 문제이다! 이전에 풀었던 문제들과 유형이 같다.

 

dx,dy가 기존에 상,하,좌,우였던 것을 나이트의 이동에 맞춰서 바꿔주기만 하면 쉽게 풀 수 있다.

 

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

dx = [-2,-1,1,2,2,1,-1,-2]
dy = [1,2,2,1,-1,-2,-2,-1]

for _ in range(t):
    l = int(input())
    sx,sy= map(int,input().split())
    ex,ey = map(int,input().split())
    visited = [ [0 for _ in range(l)]  for __ in range(l)]
    q = deque([[sx,sy]])

    while q:
        x,y = q.popleft()
        if x == ex and y == ey:
            print(visited[x][y])
            break
        for i in range(8):
            nx,ny = x + dx[i],y+ dy[i]
            if 0<= nx < l and 0 <= ny < l and visited[nx][ny] == 0:
                q.append([nx,ny])
                visited[nx][ny] = visited[x][y] +1