백준 7562 - python bfs로 푼 풀이

BFS 정복하려고 BFS문제만 엄청 푸는 중..

 

from collections import deque
import sys

input = sys.stdin.readline

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


def bfs(x, y, end_x, end_y):
    q = deque()
    #초기 위치를 큐에 넣어준다
    q.append([x, y])
    M[x][y] = 1
    while q:
        x, y = q.popleft()
        if x == end_x and y == end_y:
        # 13행에 값을 더해주기 위해 추가했던 초기값 1을 빼준다.
            return M[x][y] - 1
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            # M의 범위를 벗어나지 않고
            if 0 <= nx < len and 0 <= ny < len:
                #해당 위치를 방문하지 않았다면
                if M[nx][ny] == 0:
                    # 큐 대기열에 추가하고
                    q.append([nx, ny])
                    # 해당 위치에 현재 큐 값 + 1 해준다.
                    M[nx][ny] = M[x][y] + 1


count = int(input())
for _ in range(count):
    len = int(input())
    M = [[0] * len for _ in range(len)]
    cx, cy = map(int, input().split())
    end_x, end_y = map(int, input().split())
    if cx == end_x and cy == end_y:
        print(0)
        continue
    result = bfs(cx, cy, end_x, end_y)
    print(result)

 

---

www.acmicpc.net/problem/7562

7562번: 나이트의 이동