BOJ 7562
2020-08-09
위 문제는 백준 사이트의 알고리즘 7562 문제에 관한 설명입니다.
BOJ 7562
나이트의 이동
체스판 위에 한 나이트가 놓여져 있다.
나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다.
나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다.
첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다.
체스판의 크기는 l × l이다.
체스판의 각 칸은 두 수의 쌍 {0, …, l-1} × {0, …, l-1}로 나타낼 수 있다.
둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력
각 테스트 케이스마다 나이트가 몇 번만에 이동할 수 있는지 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[] dx = { -2, -1, 2, 1, 2, 1, -2, -1 };//나이트가 갈 수 있는 8방향
static int[] dy = { 1, 2, 1, 2, -1, -2, -1, -2 };
static int[][] map;
static boolean[][] visited;
static int n;
static int stX, stY, endX, endY;
static int count = 0;
static Queue<Point> queue = new LinkedList<Point>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int TestCase = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= TestCase; tc++) {
n = Integer.parseInt(br.readLine());
map = new int[n][n];
visited = new boolean[n][n];
StringTokenizer st = new StringTokenizer(br.readLine());
stX = Integer.parseInt(st.nextToken());
stY = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
endX = Integer.parseInt(st.nextToken());
endY = Integer.parseInt(st.nextToken());
bfs(new Point(stX, stY));
System.out.println(map[endX][endY]); //끝좌표의 값.
}
}
static void bfs(Point input) {
if (input.x == endX && input.y == endY) { //끝좌표에 다 달았으면 종료.
return;
}
visited[input.x][input.y] = true;
queue.add(input);
while (!queue.isEmpty()) { // 기본 틀.
Point temp = queue.poll();
for (int i = 0; i < 8; i++) {
int nextX = temp.x + dx[i];
int nextY = temp.y + dy[i];
if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && !visited[nextX][nextY]) { //다음으로 이동할 수 있는 위치가 범위 내라면
queue.add(new Point(nextX, nextY));
visited[nextX][nextY] = true;
map[nextX][nextY] = map[temp.x][temp.y] + 1; //현재까지 이동한 횟수에 +1 해주자.
}
}
}
}
}
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}