백준 7562 : 나이트의 이동 - 파이썬 풀이 (bfs 알고리즘 이용)

 

 

백준 7562번 나이트의 이동 문제입니다.

 

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

7562번: 나이트의 이동

 

 

 

입력 예제입니다.

첫째 줄은 테스트 케이스의 개수

그 다음 줄은 하나의 테스트 케이스로

체스판의 크기, 현재 있는 칸, 목적지 이렇게 주어집니다.

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

출력 예제입니다. 

5
28
0

 

 

나이트의 8번의 이동을 bfs로 구현해서 풀었습니다.

나이트는 (2, 1), (1, 2), (-2, 1), (-1, 2), (2, -1), (1, -2), (-2, -1), (-1, -2) 이렇게 움직이며

체스판을 넘어가면 안됩니다.

 

sys.stdin.readlind() 으로 풀어야 시간초과가 나지 않습니다. 

from collections import deque
import sys

n = int(sys.stdin.readline())

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


def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    li[x][y] = 1 #시작할 때 1로 초기화 했기 때문에
    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx, ny = dx[i] + x, dy[i] + y
            if nx < 0 or nx >= m or ny < 0 or ny >= m:
                continue
            if li[nx][ny] == 0:
                li[nx][ny] = li[x][y] + 1
                queue.append((nx, ny))


for i in range(n):
    m = int(sys.stdin.readline())
    li = [[0] * m for _ in range(m)]
    a, b = map(int, sys.stdin.readline().split())
    a1, b1 = map(int, sys.stdin.readline().split())
    bfs(a, b)
    print(li[a1][b1] - 1) #여기서 -1을 해줘야함

 

input()으로 풀면 시간초과가 납니다.