백준 7562 나이트의 이동 파이썬 풀이

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

7562번: 나이트의 이동

 
나이트는 총 8방향으로 이동한다 현재위치가 (0,0) 일때 (1,2) (-1,2) (1,-2) (-1,-2) (2,1) (2,-1) (-2,1) (-2,-1)
 그렇기에 bfs 알고리즘을 사용하여 현재 위치에 대해서 8방향의 이동을 모두 돌리고 이미 방문한 위치라면 이동하지 않게 만들었다 8방향으로 이동할때 주어진 체스판 넘어로 이동하지 못하도록 조건또한 추가해주어야한다.
 
알고리즘
1)체스판 범위 만큼 방문할 2중 리스트를 만든다
2)bfs 알고리즘을 이용하여 8방향으로 이동할때 체스판 내부이고 방문하지 않았다면 deque 에 이동한 값을 추가한다
3)deque에 값을 넣을때 count 값도 같이 넣어서 이동이 가능할때 마다 +1 씩 deque로 추가해준다
4) deque 에서 꺼낸 위치값이 목표 값하고 같아지면 count값을 출력하고 종료한다 
 
파이썬 코드

from collections import deque
idx=[1,1,-1,-1,2,2,-2,-2]
idy=[2,-2,2,-2,1,-1,1,-1]

def bfs(x,y):
    q=deque()
    q.append([x,y,0]) #(x위치,y위치,카운트)
    while q:
        ix,iy,count=q.popleft()
        if ix==endx and iy==endy: #(도달하면종료)
            print(count)
            break

        for i in range(8): # 8방향 탐색
            dx=ix+idx[i]
            dy=iy+idy[i]

            if 0<=dx<l and 0<=dy<l and vi[dx][dy]==False: #조건에 만족하면 추가
                q.append([dx,dy,count+1])
                vi[dx][dy] =True

test=int(input())

for t in range(test):
    l=int(input())
    nowx,nowy=map(int,input().split())
    endx,endy=map(int,input().split())
    vi=[[False]*l for _ in range(l)]
    bfs(nowx,nowy)