[백준] 7562번 - 나이트의 이동

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

문제

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

입력

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

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

출력

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

---

문제 풀이

import sys
from collections import deque

input = sys.stdin.readline

t = int(input())  # 테스트 케이스 수


def bfs():
    queue = deque()
    queue.append((x, y))

    while queue:
        a, b = queue.popleft()
        dx, dy = [-1, -2, -2, -1, 1, 2, 2, 1], [-2, -1, 1, 2, -2, -1, 1, 2]

        for i in range(8):
            nx, ny = a + dx[i], b + dy[i]

            if a == goal_x and b == goal_y:
                return visited[a][b] - 1

            if nx < 0 or nx >= l or ny < 0 or ny >= l:
                continue

            if visited[nx][ny] == 0:
                visited[nx][ny] = visited[a][b] + 1
                queue.append((nx, ny))


for _ in range(t):   
    l = int(input())                     # 체스판의 크기
    x, y = map(int, input().split())     # 현재 위치
    goal_x, goal_y = map(int, input().split())

    visited = [[0 for _ in range(l)] for _ in range(l)]
    visited[x][y] = 1

    print(bfs())

틀렸던 부분

처음에는 while queue: 내부에 visited[x][y] = 1 을 넣었는데 횟수가 카운트되지 않고 계속 1 혹은 2만 visited 안에 들어있었다.

생각해보니 while 내부에 visited[x][y] = 1 을 넣으니 $+1$ 되도 다시 $1$로 바뀌어서 카운트가 되지 않는 것이었다. 따라서, 방문만을 표시하는 것이면 내부에 visited[x][y] = 1을 넣어야 하고 횟수를 카운트해야할 때는 $1$부터 시작해야 하니 외부에 넣어야 한다.