https://www.acmicpc.net/problem/7562

🥚문제

---

🥚입력/출력

---

🍳코드

from collections import deque

# (x1, y1)에서 (x2, y2)까지 최소 몇 번 만에 이동하나?
def bfs(x1, y1, x2, y2, graph):
    queue = deque()
    visited = [[0]*len(graph) for _ in range(len(graph))]
    queue.append((x1, y1))
    visited[x1][y1] = 1
    while queue:
        v_x, v_y = queue.popleft()
        if v_x == x2 and v_y == y2:
            print(visited[v_x][v_y] - 1)
            break
        # 이동한 자리에 몇칸째 이동인지 기록하기
        x_movs = [-1, -2, -2, -1, 1, 2, 2, 1]
        y_movs = [-2, -1, 1, 2, -2, -1, 1, 2]
        for i in range(8):
            n_x = v_x + x_movs[i]
            n_y = v_y + y_movs[i]
            # 유효 범위
            if 0<= n_x < len(graph) and 0 <= n_y < len(graph):
                if visited[n_x][n_y] == 0:
                    visited[n_x][n_y] += visited[v_x][v_y] + 1
                    queue.append((n_x, n_y))


t = int(input())
for _ in range(t):
    l = int(input())
    chess = [[0]*l for __ in range(l)]
    # 현재 있는 칸
    current = tuple(map(int, input().split()))
    # 이동하려는 칸
    goal = tuple(map(int, input().split()))
    bfs(current[0], current[1], goal[0], goal[1], chess)

---

🧂아이디어

• 이것도 부끄럽지만 해설을 참고했다.
• Knight의 이동 규칙에 따라 BFS를 통해 이동한다. (x_movs, y_movs)
• visited에 기록해 놓은 직전 기록에 + 1 한 수를 이동할 칸에 기록해주면 그것이 지금까지 이동한 칸의 개수가 되겠다.
• 목표 지점에 도달하면 visited[x][y]를 프린트 해주는데, 이때 -1을 해주면 된다😁👍
  -1을 해주는 이유
  입출력 예제의 마지막 케이스 에서 [1][1]이 시작점이고 [1][1]이 도착점일 때 출력값이 0이라는 점에서도 -1을 해야 함을 유추할 수 있다.
  위 코드는 [x][y]칸으로 이동만 할 수 있으면 일단 +1을 해준다. (코드의 마지막 3줄 참고) 우리가 알고 싶은 것은 도착점까지의 총 칸 수가 아니라 나이트가 몇번 움직여서 이 칸까지 오는지이므로 다시 -1 해서 값을 출력해야 한다.