[BFS 알고리즘] 나이트의 이동

기출: BOJ #7562

 

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

tc = int(input())
for _ in range(tc):
    n = int(input())
    board = []
    visited = [[False for _ in range(n)] for __ in range(n)]
    start = list(map(int,input().split()))
    targetX, targetY = map(int,input().split())
    queue = [[start,0]]
    while queue:
        cur = queue.pop(0)
        curX, curY = cur[0][0], cur[0][1]
        curVal = cur[1]
        if curX==targetX and curY==targetY:
            print(curVal)
            break
        for dir in range(8):
            mx = curX + dx[dir]
            my = curY + dy[dir]
            if mx<0 or my<0 or mx>=n or my>=n: continue
            if visited[mx][my]: continue
            visited[mx][my] = True
            queue.append([[mx,my],curVal+1])