나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1

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

예제 출력 1

5
28
0

문제 풀이

시간 초과한 풀이

from collections import deque
T=int(input())
vec=[(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]

for i in range(T):
    n=int(input())
    start=list(map(int,input().split()))
    end=list(map(int,input().split()))
    visited=[]
    start.append(0)
    queue=deque([start])
    while queue:
        x,y,dis=queue.popleft()
        if x==end[0] and y==end[1]:
            print(dis,end='\n')
            break
        visited.append((x,y))
        for v in vec:
            if 0<=x+v[0]<n and 0<=y+v[1]<n:
                if (x+v[0],y+v[1]) not in visited:
                    queue.append((x+v[0],y+v[1],dis+1))

성공한 풀이

from collections import deque
T=int(input())
vec=[(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]

for i in range(T):
    n=int(input())
    start=list(map(int,input().split()))
    end=list(map(int,input().split()))
    visited=[[-1]*n for _ in range(n)]
    queue=deque([start])
    while queue:
        x,y=queue.popleft()
        if x==end[0] and y==end[1]:
            print(visited[x][y]+1,end='\n')
            break
        for v in vec:
            if 0<=x+v[0]<n and 0<=y+v[1]<n:
                if visited[x+v[0]][y+v[1]]==-1:
                    queue.append((x+v[0],y+v[1]))
                    visited[x+v[0]][y+v[1]]=visited[x][y]+1

• queue에 거리값을 넣지 않고 visited에 거리값을 넣어서 답을 출력하는 방식으로 바꾸니 시간초과가 발생하지 않았다.
• 기존 코드는 왜 시간초과가 발생했는지 이것저것 코드를 쳐보니 visited[x][y]=1 코드를 queue에서 값을 pop 할 때 넣어줘서 방향에 따라 queue에 값을 추가하는 과정에서 중복값이 들어가 더 많은 시간이 걸렸던 것 같다.
  for v in vec 코드 안에 visited[x][y]=1 를 넣어주니 visited에 중복되는 값이 없어져서 시간 초과가 발생하지 않았다.