BOJ/백준 - 7567 나이트의 이동 JAVA

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

이전에 숨바꼭질이나 토마토 같은 문제랑 비슷하다.

나이트가 이동할 수 있는 위치를 x,y로 나눠서 각각 미리 설정해 놓는다.

 

그리고 범위 안에서 방문 여부를 체크해가며, visit배열에 몇 번째 이동인지 같이 저장한다.

 

목적지에 도착하면 visit[목적지X][목적지Y]를 출력해주자

 

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int[][] visit = new int[301][301];
    static int T,I,StartX,StartY,DestX,DestY;
 
    static int[] dx = {-1,1,2,2,1,-1,-2,-2}; //나이트가 이동할 수 있는 위치
    static int[] dy = {2,2,1,-1,-2,-2,-1,1};
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
 
        while(T--!=0){
            I = Integer.parseInt(br.readLine());
 
            StringTokenizer st = new StringTokenizer(br.readLine());
            StartX = Integer.parseInt(st.nextToken());
            StartY = Integer.parseInt(st.nextToken());
 
            st = new StringTokenizer(br.readLine());
            DestX = Integer.parseInt(st.nextToken());
            DestY = Integer.parseInt(st.nextToken());
 
            bfs(StartX,StartY);
 
            //visit배열 초기화
            for(int i=0;i<I;i++){
                Arrays.fill(visit[i],0);
            }
        }
    }
    static void bfs(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x,y));
 
        while(!q.isEmpty()){
            Point cur = q.poll();
 
            if(cur.x == DestX && cur.y == DestY) {
                System.out.println(visit[cur.x][cur.y]);
                return;
            }
 
            for(int i=0;i<8;i++){
                int nxtx = cur.x+dx[i];
                int nxty = cur.y+dy[i];
 
                //체스판 범위 벗어나면
                if(nxtx<0 || nxty<0 || nxtx>=I || nxty>=I) continue;
                
                //체스판에 방문하지 않았다면
                if(visit[nxtx][nxty]==0){
                    q.offer(new Point(nxtx,nxty));
                    //이전에 이동한 횟수 + 1
                    visit[nxtx][nxty]=visit[cur.x][cur.y]+1;
                }
            }
        }
    }
}