[백준] 현명한 나이트

처음엔 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=' ')