백준 7562 나이트의 이동

해당 문제는 bfs를 통해 풀면 된다.

다만 노드를 다루는데 있어서 어떤 것이든 시간복잡도가 O(1)을 넘으면 안된다.

 

본인은 틀렸던 이유가, in / not in 으로 노드를 방문했는지 체크했기에.... 시간초과가 떳다.

이런 단순한 부분도 시간이 걸릴 수 있기 때문에 유의하자.

 

from collections import deque;
import sys;
input = sys.stdin.readline;
n = int(input().rstrip());
step = [(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2),(1,2),(2,1)];
 
def canmove(size,y,x):
  if y < 0:
    return False;
  elif y > size :
    return False
  elif x < 0:
    return False
  elif x > size :
    return False;
  else:
    return True;
 
def bfs(size,sy,sx,gy,gx):
  graph = [[0] * (size + 1) for _ in range(size + 1)]
  q = deque([]);
  q.append((sy,sx,0));
  while q:
    now = q.popleft();
    if (now[1] == gx and now[0] == gy):
      return now[2];
    if(graph[now[1]][now[0]] == 0):
      graph[now[1]][now[0]] = 1;
      for s in step:
        ty = now[0] + s[0];
        tx = now[1] + s[1];
        num = now[2] + 1;
        if (canmove(size,ty,tx)):
          q.append((ty,tx,num));
                  
for i in range(n):
  size = int(input().rstrip()) - 1;
  sx,sy = map(int,input().rstrip().split());
  gx,gy = map(int,input().rstrip().split());
  print(bfs(size,sy,sx,gy,gx));