[baekjoon]python #7562 나이트의 이동

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

7562번: 나이트의 이동

from collections import deque
def bfs(y,x,m):
    global Max
    q = deque()
    q.append((y,x,m))
    
    #방문 체크를 위한 visit배열
    visit=[[0]*n for _ in range(n)]
    visit[y][x] = 1

    while q:
        ny,nx,nm = q.popleft()
		
        #움직임 갱신해 최단경로 찾기
        if Max<nm:
            Max=nm
		
        #도착하면 while문 종료
        if ny==ey and nx == ex:
            break
		
        #나이트의 움직임
        directy=[-1,-2,-2,-1,1,2,2,1]
        directx=[-2,-1,1,2,2,1,-1,-2]
        
        for i in range(8):
            dy = directy[i] + ny
            dx = directx[i] + nx

            if 0<=dy<n and 0<=dx<n:
                if visit[dy][dx] ==0:
                    visit[dy][dx]=nm
                    q.append((dy,dx,nm+1))


t = int(input())
for tc in range(t):
    n = int(input())
    sy,sx = map(int,input().split())
    ey,ex = map(int,input().split())

    Max=0
    bfs(sy,sx,0)
    print(Max)

🎈최소 이동 횟수를 찾아야하기 때문에 BFS를 이용해서 풀었다.

🎈시작점을 입력받아 bfs 함수에 넣어주는데 이때 movement(0)도 같이 넣어준다!

🎈deque를 사용해 시간을 줄임.

🎈나이트의 최대 이동 경로가 문제에서 그림으로 주어져 있는데 위의 식의 directy,directx에 표현되어 있다.

🎈도착점에 도착하면 while문 종료

🎈전형적인 bfs틀을 맞춰 코드를 짜면 쉽게 해결되는 문제