4041 : 체스 나이트 이동
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 6
•통과: 2
•만든사람: suakii
문제 설명
$N \times N$ 크기의 체스판에서 나이트가 출발 위치 $(r_1, c_1)$에서 목표 위치 $(r_2, c_2)$까지 이동하는 최소 이동 횟수를 구하라.
나이트의 이동 방식: 한 방향으로 2칸, 수직 방향으로 1칸 이동 (L자 형태). 총 8방향으로 이동 가능하다.
체스판 밖으로는 이동할 수 없다. 만약 목표 위치에 도달이 불가능하면
[제약 조건]
• $4 \le N \le 8$
• $1 \le r_1, c_1, r_2, c_2 \le N$
• 입력되는 모든 값은 정수
나이트의 이동 방식: 한 방향으로 2칸, 수직 방향으로 1칸 이동 (L자 형태). 총 8방향으로 이동 가능하다.
체스판 밖으로는 이동할 수 없다. 만약 목표 위치에 도달이 불가능하면
-1을 출력한다.[제약 조건]
• $4 \le N \le 8$
• $1 \le r_1, c_1, r_2, c_2 \le N$
• 입력되는 모든 값은 정수
입력 설명
첫째 줄에 체스판 크기 $N$, 출발 위치 $r_1, c_1$, 목표 위치 $r_2, c_2$가 공백으로 구분되어 주어집니다.
출력 설명
최소 이동 횟수를 출력한다. 이동이 불가능하면
-1을 출력한다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 1 1 2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1도움
BFS(너비 우선 탐색)를 이용하면 최단 경로를 구할 수 있다.
나이트의 8가지 이동 방향:
$(\pm1, \pm2),\ (\pm2, \pm1)$
$N \times N$ 체스판에서는 대부분의 경우 도달 가능하지만, 특수한 경우(예: N=4, 모서리 간 이동)에 불가능한 경우가 있다.
나이트의 8가지 이동 방향:
$(\pm1, \pm2),\ (\pm2, \pm1)$
$N \times N$ 체스판에서는 대부분의 경우 도달 가능하지만, 특수한 경우(예: N=4, 모서리 간 이동)에 불가능한 경우가 있다.