[백준 7562,Java] 나이트의 이동

문제

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

풀이

 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point {
    int x;
    int y;
    int moveCount;

    Point(int x, int y, int moveCount){
        this.x = x;
        this.y = y;
        this.moveCount = moveCount;
    }
}
public class Main {
    public static int T;
    public static int N;
    public static boolean visited[][];

    public static int[] dx = {-2,-1,1,2,2,1,-1,-2};
    public static int[] dy = {1,2,2,1,-1,-2,-2,-1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        for(int t = 0; t< T; t++){
            N = Integer.parseInt(br.readLine());
            visited = new boolean[N][N];

            st = new StringTokenizer(br.readLine()," ");
            int startX = Integer.parseInt(st.nextToken());
            int startY = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine()," ");
            int endX = Integer.parseInt(st.nextToken());
            int endY = Integer.parseInt(st.nextToken());

            int result = getMoveCount(startX, startY, endX, endY);
            bw.write(String.valueOf(result)+"\n");
        }

        bw.flush();
        br.close();
        bw.close();

    }
    public static int getMoveCount(int startX, int startY, int endX, int endY){
        int totalCount = 0;

        //초기화
        visited[startX][startY] = true;
        Point kinght = new Point(startX, startY, 0);
        Queue<Point> queue = new LinkedList<>();
        queue.add(kinght);

        //bfs
        while(!queue.isEmpty()){
            Point currentKnight = queue.poll();
            if(currentKnight.x == endX && currentKnight.y ==endY){
                totalCount = currentKnight.moveCount;
            }
            else{
                for(int d =0; d<8; d++){
                    int nx = currentKnight.x + dx[d];
                    int ny = currentKnight.y + dy[d];
                    int nc = currentKnight.moveCount +1;

                    if(nx>=0 && ny>=0 && nx<N && ny<N){
                        if(!visited[nx][ny]){
                            Point nextKignht = new Point(nx, ny, nc);
                            queue.add(nextKignht);
                            visited[nx][ny] = true;
                        }
                    }
                }
            }

        }
        return totalCount;
    }
}