[백준] 7562. 나이트의 이동 python

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

문제

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

풀이과정

나이트가 이동할 수 있는 8칸을 dx, dy를 통해 나타내었다. bfs를 활용하여 방문하지 않은 노드에는 이전 노드의 값에 1을 더해줌으로써 해당 노드까지 가는데 움직인 칸 수를 나타내었다.

소스코드

import sys
input = sys.stdin

# 나이트가 이동할 수 있는 칸
dx = [-2,-2,-1,-1,1,1,2,2]
dy = [-1,1,-2,2,-2,2,-1,1]

def bfs(start, end, visit, l):
    q = [(start[0], start[1])]

    cnt = 0
    while q:
        x, y = q.pop(0)
        if [x, y] == end:
            break

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < l and 0 <= ny < l and not visit[nx][ny]:
                visit[nx][ny] = visit[x][y] + 1
                q.append((nx, ny))


t = int(input.readline().strip())
for _ in range(t):
    l = int(input.readline().strip())
    start = list(map(int,input.readline().split()))
    end = list(map(int,input.readline().split()))

    if start == end:
        print(0)
        continue

    visit = [[0] * l for _ in range(l)]
    visit[start[0]][start[1]] = 1
    bfs(start, end, visit, l)
    print(visit[end[0]][end[1]] - 1)