[백준 7562 파이썬] 나이트의 이동

문제

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

입력

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

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

출력

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

풀이

체스판의 나이트가 시작위치에서 목표위치까지 움직일 때, 최소 몇번 움직이는지 구해야한다.

bfs를 이용하여 문제를 해결하였는데

우선 나이트의 움직임에 따라 dx와 dy 리스트를 생성하였다.

그리고 방문을 나타내는 visit리스트와 움직인 횟수를 나타내는 matrix 리스트를 생성하고 0으로 초기화했는데

리스트 하나로 2가지 정보 모두 표현 가능할 것 같다.

이제 시작위치 부터 큐에 추가하고 큐가 남아있을 때까지 반복하는데

큐를 pop한 값이 목표위치와 같으면 반복을 종료한다.

같지 않다면 dx와 dy를 이용하여 이동할 수 있는 위치가 방문하지 않은 곳인지 검사하고 큐에 추가한다.

큐에 추가할 때 움직인 횟수를 matrix 리스트에 저장한다.

큐를 pop한 값과 목표위치가 같을 때 matrix[y][x] 값이 최소로 움직인 횟수이다.

 

import sys
from collections import deque
testcase = int(sys.stdin.readline().rstrip("\n"))
for _ in range(testcase):
    l = int(sys.stdin.readline().rstrip("\n"))
    sx, sy = map(int, sys.stdin.readline().rstrip("\n").split())
    fx, fy = map(int, sys.stdin.readline().rstrip("\n").split())
    matrix = [[0]*l for _ in range(l)]
    visit = [[0]*l for _ in range(l)]
    count=0
    queue = deque()
    visit[sy][sx]=1
    dx = [1,2,2,1,-1,-2,-2,-1]
    dy = [-2,-1,1,2,2,1,-1,-2]
    queue.append((sy, sx))
    while queue:
        y, x = queue.popleft()
        if (y == fy and x == fx):
            count = matrix[y][x]
            break
        for k in range(8):
            ny = y + dy[k]
            nx = x + dx[k]
            if (0 <= ny < l and 0 <= nx < l and visit[ny][nx] == 0):
                queue.append((ny, nx))
                visit[ny][nx] = 1
                matrix[ny][nx] = matrix[y][x] + 1

    print(count)