[ BOJ ] 7562 나이트의 이동 - python 문제풀이

7562 나이트의 이동

접근 : 좌표와 이동횟수를 정보에 담아 리스트에 담고 덱에서 하나씩 꺼내보면서 확인

풀이방법
1. 나이트가 한 번에 이동할 수 있는 좌표들을 구해 [행좌표, 열좌표, 이동회차] 원소로 만들기
2. 덱에 정보들을 담고 매번 확인하되, 만약 넣기 전에 일치하는 좌표가 있으면 바로 break

'''

시작 좌표 i,j
나이트가 한 번에 이동할 수 있는 좌표들
i-2,j-1 / i-2,j+1 / i-1,j-2 / i-1,j+2
i+1,j-2 / i+1,j+2 / i+2,j-1 / i+2, j+1

'''

from collections import deque
d = [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]
for tc in range(int(input())):
    n = int(input())
    ground = [[0]*n for _ in range(n)] # 방문 표시할 배열
    si,sj = map(int, input().split()) # 시작행, 시작열
    ei,ej = map(int, input().split()) # 종료행, 종료열
    ground[si][sj] = 1 # 시작행, 시작열 방문 표시
    r = 0 # 결과
    tmp = deque()
    tmp.append([si,sj,0]) # 도착할 수 있는 좌표 정보들을 담을 배열
    while tmp:
        if r != 0: # 결과를 찾았으면 중단
            break
        new = tmp.popleft() # 도착할 수 있는 점 하나를 빼기
        if new[0]==ei and new[1]==ej:
            r = new[2] # 만약 가려고 했던 좌표면 바로 중단
            break
        else:
            for i in range(8): # 도착할 수 있는 8종류의 좌표구하기
                ni = new[0]+d[i][0]
                nj = new[1]+d[i][1]
                if ni==ei and nj==ej: # 만약 그 중 도착지점이 있다면 종료
                    r = new[2]+1
                    break
                if 0<=ni<n and 0<=nj<n: # 범위가 좌표 안에 속하고
                    if ground[ni][nj] == 0: # 아직 방문한 적 없는 좌표라면
                        ground[ni][nj] = 1
                        tmp.append([ni,nj,new[2]+1]) # 다음 회차에 도착하니까 +1
    print(r)

처음에는 도달할 수 있는 좌표들을 tmp에 넣는 과정에서 도착지점과의 일치여부를 확인하지 않았는데 시간이 너무 오래걸리는 것 같아서 다시 안쪽에 확인하는 코드를 넣어줬더니 훨씬 빨라짐.