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

백준 7562 - 나이트의 이동

시간 제한 1초, 메모리 제한 256MB

# 조건

• 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

# 접근 방법

• BFS를 이용해서 풀어주면 된다.
• 다만, 상하좌우가 아닌 해당 칸들 만큼 이동하도록 방향 벡터를 잘 설정 해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs(bi, bj, goal_i, goal_j):  
    q = deque()  
    q.append((bi, bj))  
    visited = [[0] * N for _ in range(N)]  
    visited[bi][bj] = 1  
    while q:  
        si, sj = q.popleft()  
        if (si, sj) == (goal_i, goal_j):  
            return visited[si][sj] - 1  
        for d in range(8):  
            ni, nj = di[d] + si, dj[d] + sj  
            if 0<=ni<N and 0<=nj<N and visited[ni][nj] == 0:  
                q.append((ni, nj))  
                visited[ni][nj] = visited[si][sj] + 1  

T = int(input())  
di, dj = [-2, -1, 1, 2, 2, 1, -1, -2], [-1, -2, -2, -1, 1, 2, 2, 1]  
for _ in range(T):  
    N = int(input())  
    ki, kj = map(int, input().split())  
    oi, oj = map(int, input().split())  
    print(bfs(ki, kj, oi, oj))