본문 바로가기

취준/백준

[백준][Python][7562][BFS] 나이트의 이동

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

 

7562번: 나이트의 이동

문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ...

www.acmicpc.net

BFS 문제다.

 

전형적인 길찾기 문제에서 움직이는 위치만 달라진 문제다.

원래 십자모양으로 움직일 때는 dx = [1,-1,0,0], dy=[0,0,1,-1] 이런 식으로 했는데

이 움직이는 숫자만 달라진다.

 

 

import sys
from collections import deque

dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [-1, -2, -2, -1, 1, 2, 2, 1]

T = int(sys.stdin.readline())

for _ in range(T):
    q = deque()
    size = int(sys.stdin.readline())
    x, y = [int(i) for i in sys.stdin.readline().split()]
    cx, cy = [int(i) for i in sys.stdin.readline().split()]

    q.append([x, y, 0])

    v = [[False]*size for _ in range(size)]
    v[y][x] = True

    while q:
        tx, ty, tt = q.popleft()

        if cx == tx and cy == ty:
            print(tt)
            break

        for i in range(8):
            if 0 <= tx+dx[i] < size and 0 <= ty+dy[i] < size and not v[ty+dy[i]][tx+dx[i]]:
                q.append([tx+dx[i], ty+dy[i], tt+1])
                v[ty+dy[i]][tx+dx[i]] = True