7562. 나이트의 이동

문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 본문

접근 과정

• 우선 나이트의 이동에 대한 정의가 필요하다.
• 현재의 특정 좌표에서 나이트가 이동할 수 있는 경우의 수는 8가지이다.
• 나이트의 현재 위치를 큐에 넣고, 8방향으로 계속 이동시킨다.
• 체스판의 범위를 벗어나지 않는 선에서 나이트는 계속 이동하다 목표 지점에 도착한다.
  
  
• 방문처리는 필요할까?
• 다녀갔다는 표시를 남겨주지 않는다면 나이트는 무한히 이동할 것이다.
• 체스판의 범위 내에 있고, 방문하지 않았다면 체스판과 같은 사이즈의 visited 배열의 해당 좌표에 이동 횟수를 넣어준다.
  
  
• 체스판의 길이는 4부터 최대 300이고, 시간 제한은 1초이다.

풀이

# 기본 input() 입력으로 제출했을 때 시간초과가 발생했다!
# 큐를 deque로 변경하고, sys를 통해 입력을 받아오게 수정했음에도
# 시간이 꽤 오래 걸린 것을 보면 효율성에 큰 문제가 있었던 것으로 보인다.
# 효율성을 더 올릴 수 있는 방법을 생각해봐야겠다.

import sys
from collections import deque

dx = [-1, -2, -2, -1, 1, 2, 2, 1]   # 한 위치에서 나이트가 이동할 수 있는 경우
dy = [-2, -1, 1, 2, -2, -1, 1, 2]

def BFS(x, y):
    global ans

    visited = [[0] * chess_length for _ in range(chess_length)]
    Q = deque()
    Q.append([x, y])

    while Q:
        x, y = Q.popleft()
        for i in range(8):
            tx, ty = x + dx[i], y + dy[i]
            if 0 <= tx < chess_length and 0 <= ty < chess_length and not visited[tx][ty]:
                Q.append([tx, ty])
                visited[tx][ty] = visited[x][y] + 1

                if tx == target_x and ty == target_y:
                    ans = min(ans, visited[tx][ty])

for test_case in range(int(sys.stdin.readline().rstrip())):
    chess_length = int(sys.stdin.readline().rstrip())
    chess_board = [[0] * chess_length for _ in range(chess_length)]
    knight_x, knight_y = map(int, sys.stdin.readline().split())
    target_x, target_y = map(int, sys.stdin.readline().split())
    ans = 10e9

    if knight_x == target_x and knight_y == target_y:
        print(0)          # 시작 지점과 목표 지점이 동일한 경우는 바로 0을 출력한다.
        continue

    BFS(knight_x, knight_y)

    print(ans)

읽어주셔서 감사합니다!