16948번 - 데스 나이트

문제
게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (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을 출력한다.

예제 입력 1
7
6 6 0 1
예제 출력 1
4
예제 입력 2
6
5 1 0 5
예제 출력 2
-1
예제 입력 3
7
0 3 4 3
예제 출력 3
2

풀이

최단거리 문제는 BFS로 풀어보자

1. 먼저 입력받기

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(reader.readLine());
		int r,c;
		int target_r, target_c;
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		for(int i=0; i<4; i++)
		{
			r = Integer.parseInt(tokenizer.nextToken());
			c = Integer.parseInt(tokenizer.nextToken());
			target_r = Integer.parseInt(tokenizer.nextToken());
			target_c = Integer.parseInt(tokenizer.nextToken());
		}

2. 필요한 전역 변수 초기화하기

	static int N;
	static int[][] graph;
    static boolean[][] check;
	static int r,c;
	static int target_r, target_c;
	public static final int[] dx = { -2, -2, 0, 0, 2, 2 };
	public static final int[] dy = { -1, 1, -2, 2, -1, 1};

3. x,y 두개의 숫자로 이동함으로 클래스를 만든다.

private static class Location {
		int x;
		int y;
		int dist;

		public Location(int x, int y, int dist) {
			this.x = x;
			this.y = y;
			this.dist = dist;
		}
	}

4. bfs 구현

public static void BFS() {
		Queue<Location> will_visit = new LinkedList<>();
		check[r][c] = true;
		will_visit.add(new Location(r, c, 0));
		while (will_visit.isEmpty() == false) {
			Location current = will_visit.remove();
			if (current.x == target_r && current.y == target_c)
			{
				System.out.println(current.dist);
				return;
			}


			for (int i = 0; i < 6; i++) {
				int dx_x = current.x + dx[i];
				int dy_y = current.y + dy[i];
				if (dx_x >= 0 && dy_y >= 0 && dx_x < N && dy_y < N && check[dx_x][dy_y] == false) {
					check[dx_x][dy_y] = true;
					will_visit.add(new Location(dx_x, dy_y, current.dist + 1));
				}
			}
		}
        //큐가 빌때까지 도착지점에 못갔다면 -1출력
		System.out.println(-1);
		return;

	}