처음엔 BFS로 풀었고, 시간초과가 떴다. 그냥 BFS로 풀게 되면 매번 좌표를 입력받을 때 마다 똑같은 반복을 하는 것이 시간낭비같다는 생각을 하게 되었다.
그래서 문득 스친 생각은, 그냥 2차원 dp 배열을 만들고 새로운 곳 방문 시마다 카운트 값을 기록해 놓으면 좋을 것 같다는 생각을 하였다.
dp 배열에 기록해놓고, 입력을 받을 때 마다 그 배열의 값을 출력해주는 방식으로 통과되었다.
BFS함수의 마지막 인자에 -1을 넣은 것은, 큐에서 꺼내고 바로 +1을 해주기 때문에 첫 지점을 0으로 초기화 하려 함이다.
from collections import deque
def BFS(x, y, ct):
global c, d
queue = deque()
queue.append((x, y, ct))
visited[x][y] = 1
while queue:
a = queue.popleft()
dp[a[0]][a[1]] = a[2] + 1
for i in range(8):
dx = a[0] + nx[i]
dy = a[1] + ny[i]
if dx < 0 or dx >= N or dy < 0 or dy >= N:
continue
if visited[dx][dy] == 0:
visited[dx][dy] = 1
queue.append((dx, dy, a[2] + 1))
N, M = map(int, input().split())
a, b = map(int, input().split())
nx = [-1, -2, -2, -1, 1, 2, 2, 1]
ny = [-2, -1, 1, 2, 2, 1, -1, -2]
dp = [[0 for _ in range(N)] for p in range(N)]
visited = [[0 for _ in range(N)] for p in range(N)]
BFS(a - 1, b - 1, -1)
for i in range(M):
c, d = map(int, input().split())
print(dp[c - 1][d - 1], end=' ')