99클럽 코테 스터디 9일차 TIL, BFS

백준 7562: 나이트의 이동
뻔하게 풀어서 적을 말이 없다..

나이트가 갈 수 있는 칸은 [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]이니 나이트를 하나씩 옮겨 가면서 범위 확인하고, 이동횟수 t를 1 더해서 que에 더한다.

아 que.pop()할 때 visited에 더해야 할 것 같은데, 그냥 que에 집어 넣을 때 들릴 예정이니까 들렸다고 치고 visited에 넣었다.

from collections import deque

t = int(input())
for _ in range(t):
    l = int(input())
    x, y = map(int, input().split())
    goalx, goaly = map(int, input().split())
    visited = set((x, y))

    que = deque([(x, y, 0)])
    while que:
        x, y, t = que.popleft()
        if (x, y) == (goalx, goaly):
            print(t)
            break
            
        for m in [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]:
            xt = x + m[0]
            yt = y + m[1]
            if 0 <= xt < l and 0 <= yt < l and (xt, yt) not in visited:
                que.append((xt, yt, t + 1))
                visited.add((xt, yt))