[백준] 파이썬 7562번: 나이트의 이동

 

 

 

# 나이트가 최소 몇번 움직여야 원하는 칸으로 이동할 수 있는지 -> bfs
# 나이트가 이동할수있는방향 알기.
from collections import deque
t = int(input())

for _ in range(t):
    l = int(input()) # 체스판의 길이
    now = list(map(int, input().split())) # 현재 위치
    dest = list(map(int, input().split())) # 이동해야하는 위치
    graph = [[0] * l for _ in range(l + 1)] # 체스판
    visited = [[False] * l for _ in range(l + 1)] # 방문 확인할 배열

    queue = deque() # 큐 선언
    # 나이트가 이동할 수 있는 방향
    dx = [-2, -2, -1, 1, 2, 2, -1, 1]
    dy = [-1, 1, 2, 2, 1, -1, -2, -2]

    def bfs():
        queue.append(now) # 큐에 현재 위치 추가

        while queue: # 큐가 빌때까지 반복
            x, y = queue.popleft() # 큐의 첫번째 값의 좌표
            if x == dest[0] and y == dest[1]: # 만약 x, y가 목표하는 좌표와 같다면 움직이지 않아도 되니 0 리턴
                return 0

            for i in range(8): # 나이트를 움직일 수 있는 8가지 방향으로 움직임
                nx = x + dx[i] # 이동할 좌표
                ny = y + dy[i]

                if nx < 0 or nx >= l or ny < 0 or ny >= l: # 말을 움직였을때 체스판을 벗어난다면 건너뛰기  
                    continue

                if nx == dest[0] and ny == dest[1]: # 이동할 좌표가 목표하는 좌표라면
                    visited[nx][ny] = True # 방문 표시
                    return graph[x][y] + 1 # 말을 움직인 횟수추가 

                if visited[nx][ny] == False: # 이동한 곳이 방문하지 않은 곳이라면
                    queue.append([nx, ny]) # 큐에 좌표 추가
                    visited[nx][ny] = True # 방문 표시
                    graph[nx][ny] = graph[x][y] + 1 # 체스판에 말을 움직인 횟수 추가

    result = bfs()
    print(result)

 

 

 

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

7562번: 나이트의 이동