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

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

7562번: 나이트의 이동

 

이문제는 BFS를 이용해 l * l 맵 에서 처음가보는 장소가 있다면 직전거리(graph)에다 + 1을해가며

(visited)방문처리를 해주었다. 

마지막으로 graph[e_y][e_x]를 해주면 목표지점의 거리가 나올것이다.

 

 

from collections import deque
import sys
input = sys.stdin.readline

dx = [2, 2, -2, -2, 1, -1, 1, -1]
dy = [-1, 1, -1, 1, -2, -2, 2, 2]
def bfs(x, y):
    visited[y][x] = 1
    q = deque()
    q.append((y, x))

    while q:
        y, x = q.popleft()
        for i in range(8):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0<=ny<l and 0<=nx<l:
                if graph[ny][nx] == 0:
                    if not visited[ny][nx]:
                        graph[ny][nx] = graph[y][x] + 1
                        q.append((ny, nx))

T = int(input())
for i in range(T):
    l = int(input())
    graph = [[0]*l for _ in range(l)]
    visited = [[0]*l for _ in range(l)]
    s_x, s_y = map(int, input().split()) # 시작
    e_x, e_y = map(int, input().split()) # 목표
    bfs(s_x, s_y)
    print(graph[e_y][e_x])