• 현명한 나이트 : 나이트의 이동 문제를 여러 번 수행하면 풀리는 문제

---

문제 이해

이차원 좌표에서 A ⇒ B 점으로 이동하려고 한다
이 때, 말은 체스의 나이트 처럼 이동한다.

이 말은 최소 몇 번만에 B점으로 이동할 수 있는지 구하는 문제이다.

---

문제 풀이

이동에 가중치는 없다.
즉, 좌표에서 목적지까지 가중치 없는 이동을 통해 최소의 거리를 구하는 문제이다.

따라서 BFS를 통해 문제를 해결하였다.

---

코드

import java.io.*;
import java.util.*;

class Point{
	int x;
	int y;
	int length;
	
	public Point(int x,int y, int length) {
		this.x = x;
		this.y = y;
		this.length = length;
	}
	
	@Override
	public boolean equals(Object o) {
		Point p = (Point) o;
		
		return p.x==this.x && p.y==this.y;
	}
}

public class Main {
	static int N;
	static int[][] arr;
	static boolean[][] visit;
	static StringBuilder sb = new StringBuilder();
	
	static Integer dfs(Point start, Point end) {
		
		Queue<Point> points = new LinkedList<>();
		
		points.add(start);
		
		while(!points.isEmpty()) {
			Point tmp = points.poll();
			
			if(tmp.x<0 || tmp.y<0 || tmp.x>=N || tmp.y>=N) continue;
			if(visit[tmp.x][tmp.y]) continue;
            // 이미 방문했던 점은 중복 확인하지 않아도 됨.
			
			visit[tmp.x][tmp.y] = true;
			
			if(tmp.equals(end)) return tmp.length;
            // BFS의 특징. 
            // 특정 좌표가 이번에 처음 방문한 점이라면, 
            // 그 때 저장된 거리가 최소 거리
			
            // 나이트의 모든 이동
			points.add(new Point(tmp.x+2,tmp.y+1,tmp.length+1));
			points.add(new Point(tmp.x+2,tmp.y-1,tmp.length+1));
			
			points.add(new Point(tmp.x+1,tmp.y+2,tmp.length+1));
			points.add(new Point(tmp.x+1,tmp.y-2,tmp.length+1));
			
			points.add(new Point(tmp.x-2,tmp.y+1,tmp.length+1));
			points.add(new Point(tmp.x-2,tmp.y-1,tmp.length+1));
			
			points.add(new Point(tmp.x-1,tmp.y+2,tmp.length+1));
			points.add(new Point(tmp.x-1,tmp.y-2,tmp.length+1));
		}
		
		return 1;
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		int T = sc.nextInt();
		
		for(int t=0;t<T;t++) {
			N = sc.nextInt();
			arr = new int[N][N];
			visit = new boolean[N][N];
			
			sb.append(dfs(new Point(sc.nextInt(),sc.nextInt(),0), 
            			  new Point(sc.nextInt(), sc.nextInt(),0)))
              .append("\n");
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과