[백준] 7562 파이썬(python) : 나이트의 이동

7562번 : 나이트의 이동

 

 

from collections import deque
import sys
dx = [ -2, -1, 1, 2, 2, 1, -1, -2 ] #1
dy = [ -1, -2, -2, -1, 1, 2, 2, 1 ]
t = int(input())
for _ in range(t): #2
    i = int(sys.stdin.readline()) #3
    graph = [ [0] * i for _ in range(i) ]   
    x, y = map(int, sys.stdin.readline().split()) #4
    w, z = map(int, sys.stdin.readline().split())
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        if x == w and y == z: #5
            print(graph[w][z])
            break
        for j in range(8):
            nx = x + dx[j]
            ny = y + dy[j]
            if 0 <= nx < i and 0 <= ny < i:
                if graph[nx][ny] == 0: #6
                    graph[nx][ny] = graph[x][y] + 1
                    q.append((nx, ny))

 

#1 : 나이트의 이동방향을 표현

(-2, -1)을 시작으로 반시계 방향으로 dx, dy채워줌

#2 : 단순 반복이므로 반복변수 필요없음

#3 : 체스판의 크기 입력

#4 : 출발점 x, y와 도착점 w, z입력

#5 : 반복문의 탈출조건

#6 : 그래프의 각 위치에 이동횟수 입력