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

문제 설명

문제 보기

생각 과정

• 최단거리 : bfs !! / deque 이용하기 !!
• 거기까지 ...
• 나이트가 한 번에 이동할 수 있는 칸을 처음에 생각해주지 않음...

from collections import deque
testcase=int(input())
dx=[-1,-2,-2,-1,1,2,2,1]
dy=[-2,-1,1,2,2,1,-1,-2]

def bfs(x,y,target_x,target_y):
    if (x,y)==(target_x,target_y):
        return 0
        
    q=deque()
    q.append((x,y,0))
    
    while q:
        x,y,count=q.popleft()
        for i in range(8):
            nx=x+dx[i]
            ny=y+dy[i]
            
            if 0<=nx<l and 0<=ny<l and visited[nx][ny]==0 :
                visited[nx][ny]=1
                if (nx,ny)==(target_x,target_y):
                    return count+1
                else:
                    q.append((nx,ny,count+1))
                    

for _ in range(testcase):
    l=int(input())
    visited=[[0]*l for _ in range(l)]
    a,b=map(int,input().split())
    visited[a][b]=1
    target_x,target_y=map(int,input().split())
    print(bfs(a,b,target_x,target_y))