[백준/16984/파이썬] 데스 나이트

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

16948번: 데스 나이트

Problem

• 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.
• 크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.
• 데스 나이트는 체스판 밖으로 벗어날 수 없다.

조건

• 첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.
• 첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

SOL

간단한 BFS를 통한 시뮬레이션 문제이다.

#데스 나이트
from collections import deque
N=int(input())
dx=[-1,1,-2,2,-1,1]
dy=[-2,-2,0,0,2,2]

visited=[[False]*N for _ in range(N)]
sy,sx,ey,ex=map(int,input().split())

def move():
    dq=deque()
    visited[sy][sx] = True
    dq.append((sy,sx,0))
    while dq:
        y,x,d=dq.popleft()
        if y==ey and x==ex:
            print(d)
            return
        for k in range(6):
            ny=y+dy[k]
            nx=x+dx[k]
            if (0<=ny<N and 0<=nx<N) and not visited[ny][nx]:
                dq.append((ny,nx,d+1))
                visited[ny][nx] = True
    print(-1)

move()