[백준 7562]나이트의 이동

[문제]

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

[입력]

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

[출력]

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

[풀이]

이 문제는 BFS로 간단하게 풀리지만 (1) 이동할 수 있는 좌표 값이 다르다는 점이다. 나이트가 이동할 수 있는 좌표는 문제의 그림처럼 8가지 방법이다 그 이동 좌표 값을 dx, dy 1차원 배열로 초기화했다. 그리고 (2) 나이트의 시작 좌표 값을 입력받고 (3) 목표 좌표 값을 입력받는다. (4) 시작점의 좌표 값으로 BFS메소드를 실행한다. (5) 목적지 좌표에 도달하면 메소드를 종료 시키고 해당 이동 횟수를 출력해준다. (6) 목적지 좌표에 도달하지 못했을 경우 방문하지 않는 곳의 좌표라면 이동 횟수를 1씩 증가시키면서 방문처리를 해주어 나이트 위치를 큐에 넣어준다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int T, N;
    static int start_x, start_y;
    static int end_x, end_y;
    static int[][] board;
    static boolean[][] visited;
    
    // (1)
    static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
    static class night{
        int x, y, count;

        public night(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        for(int tc=0; tc<T; tc++){
            N = Integer.parseInt(br.readLine());

            board = new int[N][N];
            visited = new boolean[N][N];

			// (2)
            st = new StringTokenizer(br.readLine());
            start_x = Integer.parseInt(st.nextToken());
            start_y = Integer.parseInt(st.nextToken());
            
			// (3)
            st = new StringTokenizer(br.readLine());
            end_x = Integer.parseInt(st.nextToken());
            end_y = Integer.parseInt(st.nextToken());


            System.out.println(bfs(start_x, start_y));
        }

    }
	
    // (4)
    private static int bfs(int r, int c) {
        Queue<night> q = new ArrayDeque<>();
        visited[r][c] = true;
        q.add(new night(r, c, 0));

        while (!q.isEmpty()){
            night cur = q.poll();
            int x = cur.x;
            int y = cur.y;
            int co = cur.count;
			
            // (5)
            if(x == end_x && y == end_y) return co;

            for(int k=0; k<8; k++){
                int nx = x + dx[k];
                int ny = y + dy[k];

                if(nx < 0 || ny < 0 || nx >=N || ny >=N) continue;
				
                // (6)
                if(!visited[nx][ny]){
                    q.add(new night(nx, ny, co+1));
                    visited[nx][ny] = true;
                }
            }
        }
        return 0;
    }
}