백준 / 나이트의 이동 / 7562

Question

문제링크
Silver 1

Logic

기본 구조 :bfs
1. 나이트의 이동가능한 위치를 dx, dy로 정의한다.
2. 시작위치부터 이동 가능한 위치를 queue에 추가하여 목표 위치에 도달할 때 까지 탐색한다.

Code

from collections import deque
from sys import stdin

dx = [-1, -2, -2, -1, 1, 2, 2, 1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]

def bfs(ax,ay,bx,by):
    q = deque()
    q.append([ax,ay])
    li[ax][ay] = 1
    while(q):
        a,b = q.popleft()
        if a==bx and b ==by:
            print(li[bx][by]-1)
            return
        for i in range(8):
            x=a+dx[i]
            y=b+dy[i]
            if 0 <= x < L and 0 <= y < L and li[x][y] == 0:
                q.append([x, y])
                li[x][y] = li[a][b] + 1

for i in range(int(stdin.readline())):
    L = int(stdin.readline())
    li = [[0]*L for _ in range(L)]

    ax,ay = map(int,stdin.readline().split())
    bx,by = map(int,stdin.readline().split())

    bfs(ax,ay,bx,by)